## Luby-Rackoff backwards: Increasing security by making
block ciphers non-invertible

** Authors:** Mihir Bellare, Ted Krovetz and Phillip Rogaway

** Reference:** * Advances in Cryptology - EUROCRYPT '98, *
Lecture Notes in Computer Science, Vol. 1403, K. Nyberg, ed.,
Springer-Verlag, 1998.

** Abstract: **
We argue that the invertibility of a block cipher can reduce the security of
schemes that use it, and a better starting point for scheme design is the
non-invertible analog of a block cipher, that is, a pseudorandom function
(PRF). Since a block cipher may be viewed as a pseudorandom permutation, we are
led to investigate the reverse of the problem studied by Luby and
Rackoff, and ask, *how can one transform a PRP into a PRF in as
security-preserving a way as possible?* The solution we propose is
"data-dependent re-keying." As an illustrative special case, let *E*:
{0,1}^{n} x {0,1}^{n} -> {0,1}^{n}
be the block cipher. Then we can construct the PRF *F* from the PRP
*E* by setting *F*(*k**,*x) =
*E*(*E*(*k*,*x*),*x*).
We generalize this to allow for arbitrary block and key lengths,
and to improve efficiency. We prove strong quantitative bounds on the value of
data-dependent re-keying in the Shannon model of an ideal cipher, and take some
initial steps towards an analysis in the standard model.