Paper 2020/959

Quantum Cryptanalysis on Contracting Feistel Structures and Observation on Related-key Settings

Carlos Cid, Akinori Hosoyamada, Yunwen Liu, and Siang Meng Sim


In this paper we show several quantum chosen-plaintext attacks (qCPAs) on contracting Feistel structures. In the classical setting, a $d$-branch $r$-round contracting Feistel structure can be shown to be PRP-secure when $d$ is even and $r \geq 2d-1$, meaning it is secure against polynomial-time chosen-plaintext attacks. We propose a polynomial-time qCPA distinguisher on the $d$-branch $(2d-1)$-round contracting Feistel structure, which solves an open problem by Dong et al. In addition, we show a polynomial-time qCPA that recovers the keys of the $d$-branch $r$-round contracting Feistel structure when each round function $F^{(i)}_{k_i}$ has the form $F^{(i)}_{k_i}(x) = F_i(x \oplus k_i)$ for a public random function $F_i$. This is applicable to the Chinese block cipher standard {\texttt{SM4}}, which is a special case where $d=4$. Finally, in addition to quantum attacks under single-key setting, we also show related-key quantum attacks on balanced Feistel structures in the model that adversaries can only control part of the key difference in quantum superposition. Our related-key attacks on balanced Feistel structures can easily be extended to ones on contracting Feistel structures.

Note: This is the full version. (December 14th, 2020: some minor modifications)

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.Indocrypt 2020
symmetric-key cryptographyquantum cryptanalysiscontracting Feistel structuresSM4related-key attacks
Contact author(s)
carlos cid @ rhul ac uk
akinori hosoyamada bh @ hco ntt co jp
univerlyw @ hotmail com
crypto s m sim @ gmail com
2020-12-14: last of 2 revisions
2020-08-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carlos Cid and Akinori Hosoyamada and Yunwen Liu and Siang Meng Sim},
      title = {Quantum Cryptanalysis on Contracting Feistel Structures and Observation on Related-key Settings},
      howpublished = {Cryptology ePrint Archive, Paper 2020/959},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.