You are looking at a specific version 20200811:113806 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
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
History
2020-12-14: last of 2 revisions
2020-08-11: received
See all versions
Short URL
https://ia.cr/2020/959
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.