Information Security and Cryptography Research Group

Luby-Rackoff Ciphers from Weak Round Functions?

Ueli Maurer, Yvonne Anne Oswald, Krzysztof Pietrzak, and Johan Sjödin

Advances in Cryptology — EUROCRYPT 2006, Lecture Notes in Computer Science, Springer-Verlag, vol. 4004, pp. 391–408, May 2006, Proceedings version of [MOPS06b].

The Feistel-network is a popular structure underlying many block-ciphers where the cipher is constructed from many simpler rounds, each defined by some function which is derived from the secret key. Luby and Rackoff showed that the three-round Feistel-network – each round instantiated with a pseudorandom function secure against adaptive chosen plaintext attacks (CPA) – is a CPA secure pseudorandom permutation, thus giving some confidence in the soundness of using a Feistel-network to design block-ciphers. But the round functions used in actual block-ciphers are – for efficiency reasons – far from being pseudorandom. We investigate the security of the Feistel-network against CPA distinguishers when the only security guarantee we have for the round functions is that they are secure against non-adaptive chosen plaintext attacks (nCPA). We show that in the information-theoretic setting, four rounds with nCPA secure round functions are sufficient (and necessary) to get a CPA secure permutation. Unfortunately, this result does not translate into the more interesting pseudorandom setting. In fact, under the so-called Inverse Decisional Diffie-Hellman assumption the Feistel-network with four rounds, each instantiated with a nCPA secure pseudorandom function, is in general not a CPA secure pseudorandom permutation.

BibTeX Citation

    author       = {Ueli Maurer and Yvonne Anne Oswald and Krzysztof Pietrzak and Johan Sjödin},
    title        = {{L}uby-{R}ackoff Ciphers from Weak Round Functions?},
    booktitle    = {Advances in Cryptology --- EUROCRYPT 2006},
    pages        = {391--408},
    series       = {Lecture Notes in Computer Science},
    volume       = {4004},
    year         = {2006},
    month        = {5},
    note         = {Proceedings version of \cite{MOPS06b}},
    publisher    = {Springer-Verlag},

Files and Links