密码学报（中英文）2026，Vol.13Issue(1)：80-96,17.DOI:10.13868/j.cnki.jcr.000839
搜索最优差分和线性迹的高效方法:应用于NOEKEON和Serpent算法
Efficient Approach for Searching the Best Differential and Linear Trail:Applications to NOEKEON and Serpent
摘要
Abstract
The ability to resist differential cryptanalysis and linear cryptanalysis serves as two core metrics for evaluating the security of symmetric-key primitives.A variety of automated search tools are available for searching the best differential and linear trails for primitives.Nevertheless,these tools often exhibit inefficiency or lack generality when applied to primitives with linear layers that incorporate XOR operations.To address this problem,this study proposes an efficient and general search tool specifically designed to deal with such primitives.The Matsui's algorithm based on search patterns is enhanced by employing a memorized iterative search strategy,which significantly reduces redundant computations by effectively leveraging previous search results.The entire search process is divided into two phases:the extension of search patterns phase and the search for two-round search patterns phase.In the extension of search patterns phase,the pruning process is accelerated by leveraging the property of the linear layers of ciphers and introducing stability mask technique.In the search for two-round search patterns phase,the narrowest point technique is employed to reduce the initial search space,further enhancing the efficiency of the algorithm by integrating difference patterns and linear mask patterns.Applying the improved tool to two SPN primitives NOEKEON and Serpent,their tightest security bounds against differential and linear cryptanalysis are provided.For NOEKEON,the best differential trails up to 9 rounds and the best linear trails up to 16(full)rounds are obtained.In particular,for the first time,an 8-round best differential trail with a probability of 2-126 suitable for differential attack is identified.For Serpent,the best differential trails up to 5 rounds and the best linear trails up to 9 rounds are obtained.It is proved for the first time that the upper bound of the maximum differential probability for 10-round Serpent is 2-129,and the upper bound of the maximum linear correlation for 12-round Serpent is 2-68.关键词
差分分析/线性分析/自动化搜索/NOEKEON算法/Serpent算法Key words
differential cryptanalysis/linear cryptanalysis/automatic search/NOEKEON/Serpent分类
信息技术与安全科学引用本文复制引用
翁菁穗,张文涛,彭婷..搜索最优差分和线性迹的高效方法:应用于NOEKEON和Serpent算法[J].密码学报（中英文）,2026,13(1):80-96,17.基金项目
中国科学院稳定支持基础研究领域青年团队计划(YSBR-035) （YSBR-035）
国家自然科学基金(61379138)Chinese Academy of Sciences(CAS)Project for Young Scientists in Basic Research(YSBR-035) （61379138）
Na-tional Natural Science Foundation of China(61379138) （61379138）
