葛欣欣，李智虎，王美琴，胡凯

LowMC实例的差分枚举攻击效果分析

葛欣欣1,2，李智虎3，王美琴1,2，胡凯1,2

（1. 山东大学网络空间安全学院（研究院），山东 青岛 266237；2. 山东大学密码技术和信息安全教育部重点实验室，山东 青岛 266237；3. 中国电力科学研究院有限公司，北京 100192）

LowMC是具有低乘法复杂度特征的算法。针对低数据量和少量S盒参数下的LowMC实例，差分枚举攻击被提出，理论上可以攻击全轮LowMC算法。考虑到这种攻击是在线性层完全随机的条件下给出的，对LowMC算法在真实的线性层下抵抗差分枚举攻击的强度进行了研究。通过对关键起始轮数的研究发现，差分枚举攻击并非总是可以达到理论攻击轮数。对于某一些关键起始轮数比理论值小的LowMC实例，差分枚举攻击甚至会失败。由于LowMC算法的轮数设置基于现有攻击的效果，该分析对LowMC算法的轮数设计具有重要意义。

分组密码；LowMC算法；差分枚举攻击；关键起始轮数

1 引言

Albrecht等[1]在2015年欧密会上提出了LowMC算法。LowMC算法基于SPN结构，采用了部分非线性层和随机线性层的设计，其乘法复杂度非常低。LowMC实例是通过改变分组长度、密钥长度、每轮S盒的数量和数据复杂度的安全预期得到的。LowMC算法的低乘法复杂度特点使它在多方计算和全同态加密等场景下效率较高，自公开以后就受到了广泛关注。

本文研究了差分枚举攻击对实例化后的LowMCv2算法的攻击效果，发现对于某些参数的LowMC实例，差分枚举攻击的实际可攻击轮数并不能达到理论计算值。差分枚举攻击的可攻击轮数与LowMCv2算法的概率为1的差分路线（这条路线的轮数被称为关键起始轮数）直接相关。……