若干广义非平衡Feistel结构的量子分析研究

• 作者: 于博 孙兵 刘国强 罗宜元 张志宇
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: Simon算法 Grover算法 n-cell结构 New Structure系列结构 FBC-like结构
• 年，卷（期）: 2021,（6）
• 所属期刊栏目: 量子计算与密码分析专栏|Special Column:Quantum Computing and Cryptanalysis
• 页码范围: 960-973
• 页数: 14页
• 分类号: TP309.7
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000490

摘要

分组密码结构对密码算法的安全性有着非常重要的作用.随着量子计算的发展,以Simon算法、Grover算法等为代表的量子搜索算法,广泛应用于分组密码安全性研究领域,并产生了一定的威胁.本文首次研究了对5种广义非平衡Feistel结构的量子攻击,对n-cell结构构造了n+1轮量子区分器;对New Structure Ⅰ/Ⅲ/Ⅳ结构分别构造了6轮/9轮/5轮量子区分器;对FBC-like结构构造了3轮量子区分器,并利用Simon算法对这5种分组密码结构进行了量子区分攻击.进一步,将Simon算法和Grover算法相结合对n-cell结构、New Structure Ⅰ/Ⅲ/ⅣV结构和FBC-like结构进行了量子密钥恢复攻击,并分析了攻击的时间复杂度.攻击r＞n+1轮n-cell结构的时间复杂度为O(2(r-n-1)k/2);攻击r＞ 6/14/9轮New Structure Ⅰ/Ⅲ/Ⅳ结构的时间复杂度分别为O(2(r-6)k/2)/O(2[2k+(r-14)k|/2)/O(2[2k+(r-9)k]/2);攻击r＞5轮FBC-like结构的时间复杂度为O(2[3k+(r-5)·2k]/2).结果 表明这些攻击的效果均优于使用Grover算法进行穷举攻击.