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