[Resource Topic] 2019/243: 4-Round Luby-Rackoff Construction is a qPRP: Tight Quantum Security Bound

Welcome to the resource topic for 2019/243

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

Authors: Akinori Hosoyamada, 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.

ePrint: https://eprint.iacr.org/2019/243

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .