4-Round Luby-Rackoff Construction is a qPRP: Tight Quantum Security Bound

Akinori Hosoyamada; Tetsu Iwata

Paper 2019/243

4-Round Luby-Rackoff Construction is a qPRP: Tight Quantum Security Bound

Akinori Hosoyamada and Tetsu Iwata

Abstract

The Luby-Rackoff construction, or the Feistel construction, is one of the most important approaches to construct secure block ciphers from secure pseudorandom functions. The 3-round and 4-round Luby-Rackoff constructions are proven to be secure against chosen-plaintext attacks (CPAs) and chosen-ciphertext attacks (CCAs), respectively, in the classical setting. However, Kuwakado and Morii showed that a quantum superposed chosen-plaintext attack (qCPA) can distinguish the 3-round Luby-Rackoff construction from a random permutation in polynomial time. In addition, Ito et al. showed a quantum superposed chosen-ciphertext attack (qCCA) that distinguishes the 4-round Luby-Rackoff construction. Since Kuwakado and Morii showed the result, a problem of much interest has been how many rounds are sufficient to achieve provable security against quantum query attacks. This paper answers this fundamental question by showing that 4-rounds suffice against qCPAs. Concretely, we prove that the 4-round Luby-Rackoff construction is secure up to $O(2^{n/6})$ quantum queries. We also prove that the bound is tight by showing an attack that distinguishes the 4-round Luby-Rackoff construction from a random permutation with $O(2^{n/6})$ quantum queries. Our result is the first to demonstrate the tight security of a typical block-cipher construction against quantum query attacks, without any algebraic assumptions. To give security proofs, we use an alternative formalization of Zhandry's compressed oracle technique.

Note: Some technical errors in the proof of Proposition 5 are corrected (7/19/2020) Major Revision: Some errors in proofs are corrected. In addition, the security bound is improved. Title is changed accordingly. (6/25/2020) Minor Changes (9/13/2019) Editorial changes on the presentation. (5/18/2019) Errors in the proof of Proposition 5 are corrected, and the security bound is changed. Title is also changed accordingly. (5/2/2019)

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: A major revision of an IACR publication in ASIACRYPT 2019
Keywords: post-quantum cryptography provable security quantum security compressed oracle technique quantum chosen plaintext attacks Luby-Rackoff constructions.
Contact author(s): akinori hosoyamada bh @ hco ntt co jp
History: 2020-07-20: last of 5 revisions; 2019-02-28: received; See all versions
Short URL: https://ia.cr/2019/243
License: CC BY

BibTeX

@misc{cryptoeprint:2019/243,
      author = {Akinori Hosoyamada and Tetsu Iwata},
      title = {4-Round Luby-Rackoff Construction is a qPRP: Tight Quantum Security Bound},
      howpublished = {Cryptology ePrint Archive, Paper 2019/243},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/243}},
      url = {https://eprint.iacr.org/2019/243}
}