Turn off MathJax
Article Contents
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

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

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

Catalog

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

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

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

    Figures(8)  / Tables(2)

    Article Metrics

    Article views (190) PDF downloads(23) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return