Luby-Rackoff Ciphers from Weak Round Functions?

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

Abstract

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. We also consider other relaxations of the Luby-Rackoff construction and prove their (in)security against different classes of attacks.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. This is the full version of the paper presented at Eurocrypt 2006.
Keywords
block-ciphersFeistel-network
Contact author(s)
jsjoedin @ inf ethz ch
History
Short URL
https://ia.cr/2006/213

CC BY

BibTeX

@misc{cryptoeprint:2006/213,
author = {Ueli Maurer and Yvonne Anne Oswald and Krzysztof Pietrzak and Johan Sjödin},
title = {Luby-Rackoff Ciphers from Weak Round Functions?},
howpublished = {Cryptology ePrint Archive, Paper 2006/213},
year = {2006},
note = {\url{https://eprint.iacr.org/2006/213}},
url = {https://eprint.iacr.org/2006/213}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.