How to Encrch the Message Space of a Cipher

Reference: Fast Software Encryption 2007 (FSE), Lecture Notes in Computer Science, vol. 4593, Springer, pp. 101-118, Springer, 2007. This paper has been retracted.

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.