2003 | OriginalPaper | Buchkapitel
Luby-Rackoff: 7 Rounds Are Enough for 2 n(1 − ε) Security
verfasst von : Jacques Patarin
Erschienen in: Advances in Cryptology - CRYPTO 2003
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In [3] M. Luby and C. Rackoff have proved that 3-round random Feistel schemes are secure against all adaptative chosen plaintext attacks when the number of queries is m ≪ 2n/2. Moreover, 4-round random Feistel schemes are also secure against all adaptative chosen plaintext and chosen ciphertext attacks when m ≪ 2n/2. It was shown later that these bounds are tight for 3 and 4 rounds (see [9] or [1]).In this paper our main results are that for every ε> 0, when m ≪ 2n(1 − ε):for 4 rounds or more, a random Feistel scheme is secure against known plaintext attacks (KPA).for 7 rounds or more it is secure against all adaptative chosen plaintext attacks (CPA).for 10 rounds or more it is secure against all adaptative chosen plaintext and chosen ciphertext attacks (CPCA).These results achieve the optimal value of m, since it is always possible to distinguish a random Feistel cipher from a truly random permutation with $\mathcal{O}(2^n)$ queries, given sufficient computing power.This paper solves an open problem of [1, 9] and [17]. It significantly improves the results of [13] that proves the security against only 2$^{\frac{3n}{4}}$ queries for 6 rounds, and the results of [6] in which the 2n(1 − ε) security is only obtained when the number of rounds tends to infinity. The proof technique used in this paper is also of independent interest and can be applied to other schemes.