How to Enrich the Message Space of a Cipher
Thomas Ristenpart and
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
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 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.