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

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 \ge 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 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.