2轮Trivium的多线性密码分析

作为欧洲流密码发展计划eSTREAM的7个最终获选算法之一，Trivium的安全性考察表明至今为止还没有出现有效的攻击算法。该文针对2轮Trivium，通过找出更多线性逼近方程，对其进行了多线性密码分析，提出了一种更有效的区分攻击算法。与现有的单线性密码分析算法相比，该算法攻击成功所需的数据量明显减少，即：若能找到n个线性近似方程，在达到相同攻击成功概率的前提下，多线性密码分析所需的数据量只有单线性密码分析的1/n。该研究结果表明，Trivium的设计还存在一定的缺陷，投入实用之前还需要实施进一步的安全性分析。

Linear Cryptanalysis of 2-round Trivium with Multiple Approximations

Trivium has successfully been chosen as one of the final ciphers by eSTREAM. It has a simple and elegant structure. Although Trivium has attached a lot of interest, it remains unbroken. By finding more linear approximations, a linear cryptanalysis of 2-round Trivium is made by utilizing multiple approximations and a more efficient distinguishing attack is proposed. Compared with current single linear cryptanalysis, this method allows for a reduction in the amount of data required for a successful attack. That is to say, if n linear approximations can be found, this method can supply the success rate with 1/n of the data amount required by a simple linear cryptanalysis. This study shows that there are still some defects in the design of stream cipher Trivium, further safety analysis are needed before its going into the implementation.