关于Trivium-型序列密码代数次数估计的研究  

On Degree Evaluation of Trivium-Like Stream Ciphers

作　　者：刘晨 田甜[1] LIU Chen;TIAN Tian(PLA Strategic Support Force Information Engineering University,Zhengzhou 450001,China)

机构地区：[1]战略支援部队信息工程大学,郑州450001

出　　处：《密码学报》2021年第1期110-123,共14页Journal of Cryptologic Research

基　　金：国家自然科学基金(61672533)。

摘　　要：对于序列密码,输出密钥流比特可以视为关于密钥变元和Ⅳ变元的布尔函数,而该布尔函数的代数次数是影响密码算法安全性的重要因素;当代数次数偏低时,密码算法抵抗代数攻击、立方攻击和积分攻击的能力比较弱.目前,针对Trivium-型序列密码算法,最有效的代数次数估计方法是数值映射方法和基于MILP的可分性质方法.本文通过分析两种典型方法的特点,结合两种方法的优势,对Trivium-型算法的代数次数估计进行了改进.我们利用改进后的方法对大量随机选取的Ⅳ变量集进行了实验.实验结果表明,对于Trivium-型算法,改进后的方法能够给出比数值映射方法更紧的代数次数上界.特别地,针对Trivium算法,当输入变元为全密钥变元和全Ⅳ变元时,即80个密钥变元和80个Ⅳ变元,输出比特代数次数未达到160的最大轮数从907轮提高到912轮,这是目前已知的全变元情形下的最优代数次数估计结果.For a stream cipher, a keystream bit can be regarded as the output of a Boolean function whose variables are secret key variables and public Ⅳ variables after some transformation. The algebraic degree of the Boolean function has an important influence on the security of the cipher. If the algebraic degree is low, the cipher is vulnerable to some known attacks, such as cube attacks, algebraic attacks and integral attacks. So far there are mainly two methods to estimate the algebraic degree of a stream cipher: the numeric mapping method and the MILP-based division property method. By analyzing the advantages of these two methods, this paper improves the algebraic degree estimation of Trivium-like ciphers. As an illustration, the new method is applied to Trivium-like ciphers with randomly selected cubes. It is shown that, for Trivium-like ciphers, the improved method can reach a tighter upper bound than the numeric mapping method. In particular, as for Trivium, when taking full KEY and full Ⅳ as input variables, i.e., 80 key variables and 80 Ⅳ variables, it is found that the algebraic degree of the first output bit is less than 160 after an initialization of 912 rounds, which is five more rounds than previous best result.

关 键 词：代数次数估计 Trivium-型算法 立方攻击 零和区分器 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]