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.23919/cje.2021.00.294

Volume 32 Issue 2

Mar. 2023

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2023 > 32(2): 209-216

ZHANG Zhongya, WU Wenling, SUI Han, et al. “Quantum Attacks on Type-3 Generalized Feistel Scheme and Unbalanced Feistel Scheme with Expanding Functions”. Chinese Journal of Electronics, vol. 32 no. 2. doi: 10.23919/cje.2021.00.294

Citation:

ZHANG Zhongya, WU Wenling, SUI Han, et al. “Quantum Attacks on Type-3 Generalized Feistel Scheme and Unbalanced Feistel Scheme with Expanding Functions”. Chinese Journal of Electronics, vol. 32 no. 2. doi: 10.23919/cje.2021.00.294

Citation:

PDF( 3458 KB)

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

doi: 10.23919/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, Beijing 100178, China

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

More Information

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

Wenling WU 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)

Han SUI was born in 1986. She is working at Institute of Software, Chinese Academy of Sciences. Her research direction include the provable security theory of symmetric cryptography, and the design and analysis of authenticated encryption ciphers. ciphers. (Email: suihan@iscas.ac.cn)

Bolin WANG 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

Publish Date: 2023-03-05

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 distinguishing attacks on Type-3 GFS and UFS-E in the quantum chosen plaintext attack setting. The results of key recovery are better than those based on exhaustive search in the quantum setting.
- Quantum attacks,
- Block ciphers,
- Unbalanced Feistel scheme with expanding functions,
- Type-3 generalized Feistel scheme

FullText(HTML)

References(20)

References

[1]	H. Kuwakado and M. Morii, “Quantum distinguisher between the 3-round feistel cipher and the random permutation,” in Proceedings of the 2010 IEEE International Symposium on Information Theory, Austin, TX, USA, pp.2682–2685, 2010.
[2]	H. Kuwakado and M. Morii, “Security on the quantum-type Even-Mansour cipher,” in Proceedings 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,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, 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,” in Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 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,” in Proc. of International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, 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,” in Proceedings of International Conference on Post-Quantum Cryptography (PQCrypto 2020), Paris, France, pp.461–480, 2020.
[13]	G. Ito, A. Hosoyamada, R. Matsumoto, et al., “Quantum chosen ciphertext attacks against Feistel ciphers,” in Proceedings of the Cryptographers’ Track at the RSA Conference 2019 (CT-RSA 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. (in Chinese)
[15]	C. Cid, A, Hosoyamada, Y. Liu, et al, “Quantum cryptanalysis on contracting Feistel structures and observation on related-key settings,” in Proceedings of International Conference on Cryptology in India (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. (in Chinese)
[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,” in Proceedings of Conference on the Theory and Application of Cryptology (CRYPTO 1989), Santa Barbara, CA, USA, pp.461–480, 1990.
[19]	S. Moriai and S. Vaudenay, “On the pseudorandomness of top-level schemes of block ciphers,” in Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 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,” in Proceedings of International Conference on Security and Cryptography for Networks (SCN 2018), Amalfi, Italy, pp.386–403, 2018.