Paper 2022/1001

Quantum Security of FOX Construction based on Lai-Massey Scheme

Abstract

The Lai-Massey scheme is an important cryptographic approach to design block ciphers from secure pseudorandom functions. It has been used in the designs of IDEA and IDEA-NXT. At ASIACRYPT'99, Vaudenay showed that the 3-round and 4-round Lai-Massey scheme are secure against chosen-plaintext attacks (CPAs) and chosen-ciphertext attacks (CCAs), respectively, in the classical setting. At SAC'04, Junod and Vaudenay proposed a new family of block ciphers based on the Lai-Massey scheme, namely FOX. In this work, we analyze the security of the FOX cipher in the quantum setting, where the attacker can make quantum superposed queries to the oracle. Our results are as follows: $-$ The 3-round FOX construction is not a pseudorandom permutation against quantum chosen-plaintext attacks (qCPAs), and the 4-round FOX construction is not a strong pseudorandom permutation against quantum chosen-ciphertext attacks (qCCAs). Essentially, we build quantum distinguishers against the 3-round and 4-round FOX constructions, using Simon's algorithm. $-$ The 4-round FOX construction is a pseudorandom permutation against qCPAs. Concretely, we prove that the 4-round FOX construction is secure up to $O(2^{n/12})$ quantum queries. Our security proofs use the compressed oracle technique introduced by Zhandry. More precisely, we use an alternative formalization of the compressed oracle technique introduced by Hosoyamada and Iwata.