Volume 30 Issue 6
Nov.  2021
Turn off MathJax
Article Contents
ZHANG Zhongya, WU Wenling, WANG Bolin. Quantum Differential Collision Distinguishing Attacks on Feistel Schemes[J]. Chinese Journal of Electronics, 2021, 30(6): 1030-1037. doi: 10.1049/cje.2021.07.026
Citation: ZHANG Zhongya, WU Wenling, WANG Bolin. Quantum Differential Collision Distinguishing Attacks on Feistel Schemes[J]. Chinese Journal of Electronics, 2021, 30(6): 1030-1037. doi: 10.1049/cje.2021.07.026

Quantum Differential Collision Distinguishing Attacks on Feistel Schemes

doi: 10.1049/cje.2021.07.026
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
  • 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.
  • loading
  • 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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (198) PDF downloads(47) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return