Quantum Security of FOX Construction based on Lai-Massey Scheme

Amit Kumar Chauhan; Somitra Sanadhya

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

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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: Lai-Massey scheme FOX cipher Simon's algorithm Quantum attacks Compressed oracle technique
Contact author(s): amitchauhan @ iitj ac in
somitra @ iitj ac in
History: 2022-08-04: approved; 2022-08-04: received; See all versions
Short URL: https://ia.cr/2022/1001
License: CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2022/1001,
      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{https://eprint.iacr.org/2022/1001}},
      url = {https://eprint.iacr.org/2022/1001}
}