Paper 2019/243
4-Round Luby-Rackoff Construction is a qPRP
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, a recent work by 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, it has been a problem of much interest how many rounds are sufficient to achieve the provable security against quantum query attacks. This paper shows the answer to 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/12})$ quantum queries. We also give a query upper bound for the problem of distinguishing the 4-round Luby-Rackoff construction from a random permutation by showing a distinguishing qCPA with $O(2^{n/6})$ quantum queries. Our result is the first one that shows 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: 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)
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- post-quantum cryptographyprovable securityquantum securitycompressed oracle techniquequantum chosen plaintext attacksLuby-Rackoff constructions.
- Contact author(s)
- hosoyamada akinori @ lab 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