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

Authors: M. Bellare, T. Krovetz and P. Rogaway

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