---
_id: '3214'
abstract:
- lang: eng
text: |-
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.
acknowledgement: Most of this work was done while the K. Pietrzak was a PhD student
at ETH where he was supported by the Swiss National Science Foundation, project
No. 200020- 103847/1. Currently he is partially supported by the Commission of the
European Communities through the IST program under contract IST-2002-507932 ECRYPT.
alternative_title:
- LNCS
author:
- first_name: Ueli
full_name: Maurer, Ueli M
last_name: Maurer
- first_name: Yvonne
full_name: Oswald, Yvonne A
last_name: Oswald
- first_name: Krzysztof Z
full_name: Krzysztof Pietrzak
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Johan
full_name: Sjödin, Johan
last_name: Sjödin
citation:
ama: 'Maurer U, Oswald Y, Pietrzak KZ, Sjödin J. Luby Rackoff ciphers from weak
round functions . In: Vol 4004. Springer; 2006:391-408. doi:10.1007/11761679_24'
apa: 'Maurer, U., Oswald, Y., Pietrzak, K. Z., & Sjödin, J. (2006). Luby Rackoff
ciphers from weak round functions (Vol. 4004, pp. 391–408). Presented at the
EUROCRYPT: Theory and Applications of Cryptographic Techniques, Springer. https://doi.org/10.1007/11761679_24'
chicago: Maurer, Ueli, Yvonne Oswald, Krzysztof Z Pietrzak, and Johan Sjödin. “Luby
Rackoff Ciphers from Weak Round Functions ,” 4004:391–408. Springer, 2006. https://doi.org/10.1007/11761679_24.
ieee: 'U. Maurer, Y. Oswald, K. Z. Pietrzak, and J. Sjödin, “Luby Rackoff ciphers
from weak round functions ,” presented at the EUROCRYPT: Theory and Applications
of Cryptographic Techniques, 2006, vol. 4004, pp. 391–408.'
ista: 'Maurer U, Oswald Y, Pietrzak KZ, Sjödin J. 2006. Luby Rackoff ciphers from
weak round functions . EUROCRYPT: Theory and Applications of Cryptographic Techniques,
LNCS, vol. 4004, 391–408.'
mla: Maurer, Ueli, et al. Luby Rackoff Ciphers from Weak Round Functions .
Vol. 4004, Springer, 2006, pp. 391–408, doi:10.1007/11761679_24.
short: U. Maurer, Y. Oswald, K.Z. Pietrzak, J. Sjödin, in:, Springer, 2006, pp.
391–408.
conference:
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
date_created: 2018-12-11T12:02:03Z
date_published: 2006-07-11T00:00:00Z
date_updated: 2021-01-12T07:41:51Z
day: '11'
doi: 10.1007/11761679_24
extern: 1
intvolume: ' 4004'
month: '07'
page: 391 - 408
publication_status: published
publisher: Springer
publist_id: '3465'
quality_controlled: 0
status: public
title: 'Luby Rackoff ciphers from weak round functions '
type: conference
volume: 4004
year: '2006'
...