Quantum Differential Collision Distinguishing Attacks on Feistel Schemes

ZHANG Zhongya; WU Wenling; WANG Bolin

doi:10.1049/cje.2021.07.026

Volume 30 Issue 6

Nov. 2021

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2021 > 30(6): 1030-1037

ZHANG Zhongya, WU Wenling, WANG Bolin, “Quantum Differential Collision Distinguishing Attacks on Feistel Schemes,” Chinese Journal of Electronics, vol. 30, no. 6, pp. 1030-1037, 2021, doi: 10.1049/cje.2021.07.026

Citation:

ZHANG Zhongya, WU Wenling, WANG Bolin, “Quantum Differential Collision Distinguishing Attacks on Feistel Schemes,” Chinese Journal of Electronics, vol. 30, no. 6, pp. 1030-1037, 2021, doi: 10.1049/cje.2021.07.026

Citation:

PDF( 996 KB)

Quantum Differential Collision Distinguishing Attacks on Feistel Schemes

doi: 10.1049/cje.2021.07.026

ZHANG Zhongya^{1,2,3
,
,},
WU Wenling^1,2,
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 100190, China;
3. Luoyang Normal University, Luoyang 471934, China

Funds:

This work is supported by the National Natural Science Foundation of China (No.62072445, No.61672509).

Received Date: 2020-11-04
Rev Recd Date: 2021-01-18

Available Online: 2021-09-23

Publish Date: 2021-11-05

Abstract

Abstract

Feistel schemes are important components of symmetric ciphers, which have been extensively studied in the classical setting. We examine the extension methods of differential distinguishers of Feistel key-function and Feistel function-key schemes. The schemes are subjected to quantum differential collision distinguishing attacks based on the methods. The results show that the complexity is lower than that of differential attacks using only Grover algorithm, and the complexity of differential collision attack based on the Brassard-Høyer-Tapp and Grover algorithms is lower than that of quantization when using only the Grover algorithm. The results also show that different algorithms and methods can be combined to produce a more effective cryptanalysis approach. This provides a research direction for postquantum cryptographic analysis and design.
- Quantum computing,
- Block cipher,
- Feistel scheme,
- Differential attacks,
- Distinguishing attacks

FullText(HTML)

References(21)

References

J. Li, N. Li, Y. Zhang, et al., "A survey on quantum cryptography", Chinese Journal of Electronics, Vol.27, No.2, pp.223-228, 2018.

S. H. Su and G. D. Sun, "Analysis of a public-key cryptograph based on multi-discrete logarithm problems", Acta Electronica Sinica, Vol.46, No.1, pp.218-222, 2018. (in Chinese)

W. N. Zhu and Z. H. Liu, "User identifying algorithm based on quantum computing", Acta Electronica Sinica, Vol.46, No.1, pp.24-30, 2018. (in Chinese)

J. H. Liu, H. G. Zhang and J. W. Jia, "Cryptanalysis of schemes based on polynomial symmetrical decomposition", Chinese Journal of Electronics, Vol.26, No.6, pp.1139-1146, 2017.

Y. L. Wang and Q. L. Xu, "Principle and research progress of quantum computation and quantum cryptography", Journal of Computer Research and Development, Vol.57, No.10, pp.2015-2026, 2020. (in Chinese)

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.

D. R. Simon, "On the power of quantum computation", SIAM J. Comput, Vol.16, No.5, pp.1474-1483, 1997.

G. Brassard, P. Høyer and A. Tapp, "Quantum cryptanalysis of hash and claw-free functions", LATIN'98:Theoretical Informatics, Campinas, Brazil, pp.163-169, 1998.

A. Hosoyamada and Y. Sasaki, "Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound", Advances in Cryptology-EUROCRYPT 2020, Zagreb, Croatia, pp.249-279, 2020.

M. Zhandry, "How to construct quantum random functions", Proc. of the 53rd Annual IEEE Symposium on Foundations of Computer Science, New Brunswick, NJ, USA, pp.679-687, 2012.

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.

K. Aoki, T. Ichikawa, M. Kanda, et al., "Camellia:A 128-bit block cipher suitable for multiple platforms-design and analysis", 7th Annual International Workshop, SAC 2000, Ontario, Canada, pp.39-56, 2000.

GOST 28147-89:1989, Cryptographic Protection for Data Processing Systems, Government Committee of the USSR for Standards.

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.

G. Ito, A. Hosoyamada, R. Matsumoto, et al., "Quantum chosen ciphertext attacks against Feistel ciphers", The Cryptographers' Track at the RSA Conference 2019, San Francisco, CA, USA, pp.391-411, 2019.

X. Y. Dong, Z. Li and X. Y. Wang, "Quantum cryptanalysis on some generalized Feistel schemes", Science China (Information Sciences), 2019, Vol.62, No.2, pp.180-191.

B. Y. Ni and X. Y. Dong, "Improved quantum attack on type-1 generalized feistel schemes and its application to CAST-256", Journal of Electronics and Information Technology, Vol.42, No.2, pp.295-306, 2020. (in Chinese)

E. Biham and A. Shamir, "Differential cryptanalysis of DESlike cryptosystems", Advances in Cryptology -CRYPTO'90, 10th Annual International Cryptology Conference, Santa Barbara, California, USA, pp.2-21, 1991.

M. Kaplan, G. Leurent, A. Leverrier, et al., "Quantum differential and linear cryptanalysis", IACR Transactions on Symmetric Cryptology, Vol.2016, No.1, pp.71-94, 2016.

Q. Zhou, S. F. Lu, Z. G. Zhang, et al., "Quantum differential cryptanalysis", Quantum Information Processing, Vol.14, No.6, pp.2101-2109, 2015.

Matsui Mitsuru, "On correlation between the order of Sboxes and the strength of DES", Advances in CryptologyEurocrypt'94, Perugia, Italy, pp.366-375, 1994.

Relative Articles

Supplements(0)

Cited By

Proportional views