A New Method for Searching Cubes and Its Application to 815-Round Trivium  

作　　者：LIU Chen TIAN Tian QI Wenfeng 

机构地区：[1]PLA Strategic Support Force Information Engineering University,Zhengzhou 450001,China

出　　处：《Journal of Systems Science & Complexity》2023年第5期2234-2254,共21页系统科学与复杂性学报（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant No.61672533。

摘　　要：The cube attack proposed by Dinur and Shamir is one of the most important key-recovery attacks against Trivium.Recently division property based cube attacks have been extensively studied and significantly improved.In particular,the MILP modeling technique for the three-subset division property without unknown subset proposed by Hao,et al.at EUROCRYPT 2020 and the new technique with nested monomial predictions proposed by Hu,et al.at ASIACRYPT 2021 are best techniques to recover exact superpolies in division property based cube attacks.Consequently,at this state of the art,whether a superpoly can be recovered in division property based cube attacks is mainly decided by the scale of the superpoly,that is,the number of terms.Hence the choice for proper cubes corresponding to low-complexity superpolies is more critical now.Some effective cube construction methods were proposed for experimental cube attacks,but not applicable to division property based cube attacks.In this paper,the authors propose a heuristic cube criterion and a cube sieve algorithm,which can be combined with the three-subset division property to recover a number of superpolies.Applied to815-round Trivium,the authors recovered 417 superpolies from 441 cubes obtained by our algorithm of sizes between 41 and 48.The success rate is 94.56%.There are 165 non-constant superpolies with degree less than 14.In order to demonstrate the significance of the new algorithm,the authors tested the best superpoly recovery technique at EUROCRYPT 2020 using random cubes of similar sizes on 815-round Trivium.The experimental result shows that no cube could be completely recovered within a given period of time because the superpolies for random cubes are too complex.

关 键 词：Cube attacks division property key-recovery attacks trivium 

分 类 号：TN918.4[电子电信—通信与信息系统]