Quantum Attacks on Type-3 Generalized Feistel Scheme and Unbalanced Feistel Scheme with Expanding Functions

ZHANG Zhongya; WU Wenling; SUI Han; WANG Bolin

doi:10.1049/cje.2021.00.294

Article Contents

Article Navigation > Chinese Journal of Electronics > 2022 > Uncorrected proof

ZHANG Zhongya, WU Wenling, SUI Han, WANG Bolin. Quantum Attacks on Type-3 Generalized Feistel Scheme and Unbalanced Feistel Scheme with Expanding Functions[J]. Chinese Journal of Electronics. doi: 10.1049/cje.2021.00.294

Citation:

ZHANG Zhongya, WU Wenling, SUI Han, WANG Bolin. Quantum Attacks on Type-3 Generalized Feistel Scheme and Unbalanced Feistel Scheme with Expanding Functions[J]. Chinese Journal of Electronics. doi: 10.1049/cje.2021.00.294

Citation:

PDF( 3536 KB)

Quantum Attacks on Type-3 Generalized Feistel Scheme and Unbalanced Feistel Scheme with Expanding Functions

doi: 10.1049/cje.2021.00.294

ZHANG Zhongya^{1, 2, 3
,},
WU Wenling^{1, 2
,},
SUI Han^{1, 4
,},
WANG Bolin^{1, 2
,}

1.
Trusted Computing and Information Assurance Laboratory, Institute of Software,Chinese Academy of Sciences, Beijing 100190, China
2.
University of Chinese Academy of Sciences, Beijing 100049, China
3.
Luoyang Normal University, Luoyang 471934, China
4.
State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100178, China

Funds: This work is supported by the National Natural Science Foundation of China (No.62072445) and the National Key Research and Development Program of China (No. 2021YFB3100100)

More Information

Author Bio:
was born in 1985. He is a Ph.D. in Cyberspace Security. His main research interests include design and cryptanalysis of block ciphers and quantum computing. (Email: zzycrypto@163.com)

was born in 1966. She is a researcher, and Ph.D. supervisor in Chinese Academy of Sciences. Her main research interests include design and cryptanalysis of block ciphers. (Email: wenling@iscas.ac.cn)

was born in 1986. She is a Ph.D. in Information Security, the main research direction is the provable security theory of symmetric cryptography, and the design and analysis of authenticated encryption ciphers. (Email: suihan@iscas.ac.cn)

was born in 1995. She is currently working toward the Ph.D degree at Institute of Software, Chinese Academy of Sciences. Her main research interests include design and analysis of block ciphers. (Email: bolin2018@iscas.ac.cn)
Received Date: 2021-09-30
Accepted Date: 2021-12-31

Available Online: 2022-01-04

Abstract

Abstract

Quantum algorithms are raising concerns in the field of cryptography all over the world. A growing number of symmetric cryptography algorithms have been attacked in the quantum setting. Type-3 generalized Feistel scheme (GFS) and unbalanced Feistel scheme with expanding functions (UFS-E) are common symmetric cryptography schemes, which are often used in cryptographic analysis and design. We propose quantum attacks on the two Feistel schemes. For $ d $-branch Type-3 GFS and UFS-E, we propose distinguishing attacks on $(d+1)$-round Type-3 GFS and UFS-E in polynomial time in the quantum chosen plaintext attack (qCPA) setting. We propose key recovery by applying Grover's algorithm and Simon's algorithm. For $ r $-round $ d $-branch Type-3 GFS with $ k $-bit length subkey, the complexity is $O({2^{(d - 1)(r - d - 1)k/2}})$ for $r\ge d + 2$. The result is better than that based on exhaustive search by a factor ${2^{({d^2} - 1)k/2}}$. For $ r $-round $ d $-branch UFS-E, the attack complexity is $O({2^{(r - d - 1)(r - d)k/4}})$ for $d + 2 \le r \le 2d$, and $O({2^{(d - 1)(2r - 3d)k/4}})$ for $r > 2d$. The results are better than those based on exhaustive search by factors ${2^{(4rd - {d^2} - d - {r^2} - r)k/4}}$ and ${2^{3(d - 1)dk/4}}$ in the quantum setting, respectively.
- Quantum attacks,
- Block ciphers,
- Unbalanced Feistel scheme with expanding functions,
- Type-3 generalized Feistel scheme

FullText(HTML)

References(21)

References

[1]	H. Kuwakado and M. Morii, “Quantum distinguisher between the 3-round feistel cipher and the random permutation,” Proc of the 2010 IEEE International Symposium on Information Theory, Austin, Texas, USA, pp. 2682–2685, 2010.
[2]	H. Kuwakado and M. Morii, “Security on the quantum-type Even-Mansour cipher,” Proc of the International Symposium on Information Theory and its Applications, ISITA 2012, Honolulu, HI, USA, pp. 312–316, 2012.
[3]	S. Even and Y. Mansour, “A construction of a cipher from a single pseudorandom permutation,” J. Cryptology, vol.10, no.3, pp.151–162, 1997. doi: 10.1007/s001459900025
[4]	M. Luby and C. Rackoff, “How to construct pseudorandom permutations from pseudorandom functions,” SIAM J. Comput, vol.17, no.2, pp.373–386, 1988. doi: 10.1137/0217022
[5]	L.K. Grover, “A fast quantum mechanical algorithm for database search,” Proc. of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, USA, pp. 212–219, 1996.
[6]	D.R. Simon, “On the power of quantum computation,” SIAM J. Comput, vol.16, no.5, pp.1474–1483, 1997.
[7]	G. Leander and A. May, “Grover meets Simon – quantumly attacking the FX construction,” ASIACRYPT 2017, Springer, Cham, pp. 161–178, 2017.
[8]	X.Y. Dong, Z. Li and X.Y. Wang, “Quantum cryptanalysis on some generalized Feistel schemes,” Science China (Information Sciences), vol.62, no.2, pp.180–191, 2019.
[9]	X. Y. Dong and X. Y. Wang, “Quantum key-recovery attack on Feistel structures,” Science China (Information Sciences), vol.61, no.10, pp.1–7, 2018.
[10]	X. Dong, B. Dong and X. Wang, “Quantum attacks on some Feistel block ciphers,” Designs, Codes and Cryptography, vol.88, no.6, pp.1179–1203, 2020. doi: 10.1007/s10623-020-00741-y
[11]	X. Dong, S. Sun, D. Shi, F Gao, et al., “Quantum collision attacks on AES-like hashing with low quantum random access memories.” ASIACRYPT 2020, Springer, Cham, pp. 727–757, 2020.
[12]	S. Hodžić, L. Ramkilde and A. Kidmose, “On Quantum Distinguishers for Type-3 Generalized Feistel Network Based on Separability,” PQCrypto 2020, Springer, Cham, pp. 461–480, 2020.
[13]	G. Ito, A. Hosoyamada, R. Matsumoto, et al., “Quantum chosen ciphertext attacks against Feistel ciphers,” CTRSA 2019, San Francisco, CA, USA, pp. 391–411, 2019.
[14]	Q. D. You, X. Qian, X. Zhou, et al., “Research on Quantum Cryptanalysis on SMS4-like Structure and NBC Algorithm,” Journal of Cryptologic Research, vol.7, no.6, pp.864–874, 2020.
[15]	C. Cid, A, Hosoyamada, Y. Liu, et al, “Quantum Cryptanalysis on Contracting Feistel Structures and Observation on Related-key settings,” INDOCRYPT 2020, Bangalore, India, pp. 373–394, 2020.
[16]	X. Qian, Q. D. You, X. Zhou, et al., “Quantum Attack on MARS-like Feistel Schemes,” Journal of Cryptologic Research, vol.8, no.3, pp.417–431, 2021.
[17]	H. Feistel, W.A. Notz and J.L. Smith, “Some cryptographic techniques for machine-to-machine data communications,” Proc. of the IEEE, vol.63, no.11, pp.1545–1554, 1975. doi: 10.1109/PROC.1975.10005
[18]	Y. Zheng, T. Matsumoto and H. Imai, “On the construction of block ciphers provably secure and not relying on any unproved hypotheses,” CRYPTO 1989, Springer, New York, pp. 461–480, 1990.
[19]	S. Moriai and S. Vaudenay, “On the pseudorandomness of top-level schemes of block ciphers,” ASIACRYPT 2000. Springer, Heidelberg, pp. 289–302, 2000.
[20]	A. Hosoyamada and Y. Sasaki, “Quantum Demiric-Sel¸cuk meet-in-the-middle attacks: applications to 6-round generic Feistel constructions,” SCN 2018, Springer, Cham, pp. 386–403, 2018.
[21]	J. Kilian and P. Rogaway, “How to protect DES against exhaustive key search,” CRYPTO 1996, Springer, Heidelberg, pp. 252–267, 1996.