Cryptology ePrint Archive: Report 2007/109

How to Enrich the Message Space of a Cipher

Thomas Ristenpart and Phillip Rogaway

Abstract: Given (deterministic) ciphers $\calE$ and~$E$ that can encipher messages of $\el$ and $n$ bits, respectively, we construct a cipher~$\calE^*=XLS[\calE,E]$ that can encipher messages of $\el+s$ bits for any $s<n$. Enciphering such a string will take one call to~$\calE$ and two calls to~$E$. We prove that~$\calE^*$ is a strong pseudorandom permutation as long as~$\calE$ 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.

Category / Keywords: secret-key cryptography / Deterministic encryption, enciphering scheme, symmetric encryption, length-preserving encryption, multipermutation

Publication Info: Preliminary version appears in FSE 2007.

Date: received 25 Mar 2007

Contact author: tristenp at cs ucsd edu

Available formats: PDF | BibTeX Citation

Version: 20070326:072155 (All versions of this report)

Discussion forum: Show discussion | Start new discussion