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.

Full version available in PDF or PostScript.

Rogaway's home page.