Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography

Authors: Mihir Bellare and Phillip Rogaway

Reference: Advances in Cryptology - Asiacrypt '00 , Lecture Notes in Computer Science, vol. 1976, T. Okamoto, ed., Springer-Verlag, pp. 317-330, December 2000.

Abstract: We investigate the following approach to symmetric encryption: first encode the message via some keyless transform, and then encipher the encoded message, meaning apply a permutation F(K,.) based on a shared key K. We provide conditions on the encoding functions and the cipher which ensure that the resulting encryption scheme meets strong privacy (eg. semantic security) and/or authenticity goals. The encoding can either be implemented in a simple way (eg. prepend a counter and append a checksum) or viewed as modeling existing redundancy or entropy already present in the messages, whereby encode-then-encipher encryption provides a way to exploit structured message spaces to achieve compact ciphertexts.

Paper available in PostScript or pdf

Rogaway's home page.