Paper 2022/1001

Quantum Security of FOX Construction based on Lai-Massey Scheme

Amit Kumar Chauhan, Indian Institute of Technology Jodhpur
Somitra Sanadhya, Indian Institute of Technology Jodhpur

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.

Available format(s)
Secret-key cryptography
Publication info
Lai-Massey scheme FOX cipher Simon's algorithm Quantum attacks Compressed oracle technique
Contact author(s)
amitchauhan @ iitj ac in
somitra @ iitj ac in
2022-08-04: approved
2022-08-04: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-ShareAlike


      author = {Amit Kumar Chauhan and Somitra Sanadhya},
      title = {Quantum Security of {FOX} Construction based on Lai-Massey Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1001},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.