| 引用本文： |
-
郭旭,史丹萍,胡磊,郭一,陈芷如.MILP-Crossbred算法对LowMC的代数攻击[J].信息安全学报,已采用 [点击复制]
- Guo Xu,Shi danPing,Hu Lei,Guo Yi,Chen Zhiru.MILP-Crossbred Algebraic Attacks on LowMC[J].Journal of Cyber Security,Accept [点击复制]
|
|
| 摘要: |
| 对称密码算法LowMC具有低乘法复杂度的性质，被广泛应用于安全多方计算等密码协议中，同时也面临着密码分析挑战。简化的Crossbred算法经常用于对这类密码算法的代数攻击中，该算法在求解二次布尔方程组时将变量任意分割为两组，这一分割策略会导致次优的求解复杂度。本文使用混合整数线性规划技术（MILP）建模简化Crossbred算法实现优化，提出MILP-Crossbred算法。该模型自动化搜索使简化Crossbred算法的复杂度更优的变量分割策略。将该方法应用于分析LowMC时，本文提出的方案能够攻击更多轮数。针对分组长度为128和192比特且每轮包含1个S盒的LowMC实例， MILP-Crossbred算法分别能够将此前攻击轮数提升7轮和5轮。此外，与前人的结果相比，本文提出的MILP-Crossbred算法降低了求解二次方程组的复杂度：对于分组长度192比特且每轮1个S盒的LowMC实例，复杂度降低2^1.6；对于分组长度192和256比特且每轮10个S盒的LowMC实例，复杂度分别降低2^1.5和2^1.3。 |
| 关键词: LowMC 代数攻击 混合整数线性规划 Crossbred算法 |
| DOI： |
| 投稿时间：2026-01-16修订日期：2026-04-01 |
| 基金项目:国家自然科学基金项目(No. 62422214，No. 62472421，No. 62172410)；国家密码科学基金项目(No. 2025NCSF01012)；中国科学院战略性先导科技专项(No. XDB0690200)；中国科学院青年创新促进会；中国科学院国际伙伴计划(No. 205GJHZ2024005FN) |
|
| MILP-Crossbred Algebraic Attacks on LowMC |
|
Guo Xu, Shi danPing, Hu Lei, Guo Yi, Chen Zhiru
|
| (Institute of Information Engineering) |
| Abstract: |
| The symmetric cipher LowMC, characterized by its low multiplicative complexity, is widely employed in cryptographic protocols such as secure multi-party computation, while also facing challenges in cryptanalysis. The Crossbred algorithm is often used in algebraic attacks against this type of symmetric cipher, this algorithm arbitrarily partitions variables into two groups when solving the quadratic Boolean equations system, which leads to suboptimal computational complexity. This paper introduces a novel approach MILP-Crossbred algorithm by modeling the Crossbred algorithm within a Mixed-Integer Linear Programming (MILP) framework. This model automatically searches for variable partitioning strategies that optimize the complexity of the Crossbred algorithm. When applied to LowMC, our MILP-Crossbred algorithm can attack more rounds. For block sizes of 128 and 192 bits with 1 S-box per round, our method can attack 7 and 5 additional rounds, respectively. Additionally, the MILP-Crossbred algorithm demonstrates a measurable reduction in attack complexity compared to previous manual results. For block size of 192 bits with 1 S-box per round, the complexity of solving quadratic equations by our MILP-Crossbred algorithm is reduced by 2^1.6. For block sizes of 192 and 256 bits with 10 S-boxes per round, the complexity of solving quadratic equations by our MILP crossbred-like algorithm is reduced by 2^1.5 and 2^1.3, respectively. |
| Key words: LowMC Algebraic attack Mixed-Integer Linear Programming Crossbred Algorithm |
