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

Mihir Bellare and Phillip Rogaway
CS2000-0646
March 6, 2000

We investigate the following approach to symmetric encryption: first \textit{encode\/} the message in some trivial way (eg., prepend a counter and append a checksum), and then \textit{encipher\/} the encoded message. Here encipher'' means to apply a cipher (i.e.~pseudorandom permutation) $F_\key$, where~$\key$ is the shared key. We show that if the encoding step incorporates a nonce (counter or randomness), in any way at all, then the resulting encryption scheme will be semantically secure. And we show that if the encoding step incorporates redundancy, in any form at all, then, as long as the receiver verifies the presence of this redundancy in the deciphered string, the resulting encryption scheme achieves message authenticity. The second result helps explain and justify the prevalent misunderstanding that encrypting messages which have redundancy is enough to guarantee message authenticity: the statement is actually true if encrypting'' is understood as enciphering.'' Encode-then-encipher encryption can be used to robustly and efficiently exploit structured message spaces. If one is presented with messages known \textit{a~priori} to contain something that behaves as a nonce, then privacy can be obtained with no increase in message length, and no knowledge of the structure of the message, simply by enciphering the message. Similarly, if one is presented with messages known \textit{a~priori} to contain adequate redundancy, then message authenticity can be obtained with no increase in message length, and no knowledge of the structure of the message, simply by enciphering the message.

## How to view this document

• Display an overview of the document in one of the following formats.

• Display a selected page in one of the following formats (document has 15 pages).
• Display the whole document in one of the following formats.