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

Quantum Cryptanalysis on Some Generalized Unbalanced Feistel Networks

分组密码结构对密码算法的安全性有着非常重要的作用.随着量子计算的发展,以Simon算法、Grover算法等为代表的量子搜索算法,广泛应用于分组密码安全性研究领域,并产生了一定的威胁.本文首次研究了对5种广义非平衡Feistel结构的量子攻击,对n-cell结构构造了n+1轮量子区分器;对New Structure Ⅰ/Ⅲ/Ⅳ结构分别构造了6轮/9轮/5轮量子区分器;对FBC-like结构构造了3轮量子区分器,并利用Simon算法对这5种分组密码结构进行了量子区分攻击.进一步,将Simon算法和Grover算法相结合对n-cell结构、New Structure Ⅰ/Ⅲ/Ⅳ结构和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算法进行穷举攻击.

The structure of block ciphers plays a very important role in the security of block ciphers.With the development of quantum computing,quantum search algorithms pose a certain threat to the security of traditional block ciphers.Simon algorithm and Grover algorithm are two representative quantum search algorithms which have been widely used in the cryptanalysis of block ciphers.This paper firstly studies the quantum attack on 5 kinds of generalized unbalanced Feistel networks.This paper constructs an n+1 rounds quantum distinguisher about n-cell network,a 6/9/5rounds quantum distinguisher about New Structure Ⅰ/Ⅲ/Ⅳ and a 3 rounds quantum distinguisher about FBC-like network.Moreover,combining Simon algorithm with Grover algorithm,this paper proposes a quantum key recover attack on n-cell network,New Structure Ⅰ/Ⅲ/Ⅳ networks,and FBC-like network respectively,and the time complexities of attacks are analyzed.More specifically,for r>n+1 rounds n-cell network,the time complexity is O(2^((r-n-1)k/2));for r>6/14/9 rounds New Structure Ⅰ/Ⅲ/Ⅳ networks,the time complexity is O(2^((r-6)k/2))/O(2^([2k+(r-14)k]/2))/O(2^([2k+(r-9)k]/2));for r>5 rounds FBC-like network,the time complexity is O(2^([3k+(r-5)·2k]/2)).The results show that these attacks are more efficient than the quantum brute force attack using Grover algorithm.