Quantum Cryptanalysis on Some Generalized Unbalanced Feistel Networks [若干广义非平衡 Feistel 结构的量子分析研究]

作者：Yu B.; Sun B.^*; Liu G.-Q.; Luo Y.-Y.; Zhang Z.-Y.

来源：密码学报（中英文）, 2021, 8(6): 960-973.

DOI：10.13868/j.cnki.jcr.000490

• FBC-like network
• Grover algorithm
• n-cell network
• New Structure networks
• Simon algorithm

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/5 rounds quantum distinguisher about New Structure I/III/IV 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 I/III/IV 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 I/III/IV 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.

• 单位
  信息安全国家重点实验室; 中国科学院大学