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

Akinori Hosoyamada; Tetsu Iwata

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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}
}