CryptoDB
4-Round Luby-Rackoff Construction is a qPRP
| Authors: | |
|---|---|
| Download: | |
| 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- 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. recently 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 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 to demonstrate the 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. |
BibTeX
@article{asiacrypt-2019-30013,
title={4-Round Luby-Rackoff Construction is a qPRP},
booktitle={Advances in Cryptology – ASIACRYPT 2019},
series={Advances in Cryptology – ASIACRYPT 2019},
publisher={Springer},
volume={11921},
pages={145-174},
doi={10.1007/978-3-030-34578-5_6},
author={Akinori Hosoyamada and Tetsu Iwata},
year=2019
}