International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

How to Enrich the Message Space of a Cipher

Authors:
Thomas Ristenpart
Phillip Rogaway
Download:
URL: http://eprint.iacr.org/2007/109
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13391,
  title={How to Enrich the Message Space of a Cipher},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Deterministic encryption, enciphering scheme, symmetric encryption, length-preserving encryption, multipermutation},
  url={http://eprint.iacr.org/2007/109},
  note={Preliminary version appears in FSE 2007. tristenp@cs.ucsd.edu 13597 received 25 Mar 2007},
  author={Thomas Ristenpart and Phillip Rogaway},
  year=2007
}