** 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.

** Ref:** Extended abstract was in Advances in Cryptology- Eurocrypt 98
Proceedings, Lecture Notes in Computer Science Vol. 1403, K. Nyberg ed,
Springer-Verlag, 1998. Full paper available below.

** Full paper: ** Available as compressed
postscript, postscript or
pdf. ( Help if this doesn't work).