Cryptology ePrint Archive: Report 2020/959

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

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

Abstract: 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.

Category / Keywords: secret-key cryptography / symmetric-key cryptography, quantum cryptanalysis, contracting Feistel structures, SM4, related-key attacks

Original Publication (with major differences): Indocrypt 2020

Date: received 5 Aug 2020, last revised 13 Dec 2020

Contact author: carlos cid at rhul ac uk,akinori hosoyamada bh@hco ntt co jp,univerlyw@hotmail com,crypto s m sim@gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20201214:015128 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]