How to Enrich the Message Space of a Cipher

Authors:
Thomas Ristenpart and Phillip Rogaway

Abstract:
Given (deterministic) ciphers E and E that can encipher messages of l and n bits, respectively, we construct a cipher E*=XLS[E,E] that can encipher messages of l+s bits for any s<n. Enciphering such a string will take one call to E and two calls to E. We prove that E* is a strong pseudorandom permutation as long as E and E are. Our construction works even in the tweakable and VIL (variable-input-length) settings. It makes use of a multipermutation (a pair of orthogonal Latin squares), a combinatorial object not previously used to get a provable-security result.

References:
An extended abstract appears in Fast Software Encryption - FSE 2007, Lecture Notes in Computer Science Vol. 4593, pp. 101--118, A. Biryukov ed., Springer-Verlag, 2007.



Full Version:
Full version of the paper: pdf.



List of Updates:
Feruary 26, 2015 - This paper has been retracted. There is a bug in the main proof, discovered by Mridul Nandi. See the PDF above for details.
March 27, 2006 - Put up full version.