Department of Computer Science & Engineering

We investigate the following approach to symmetric encryption: first encode the message in some trivial way (eg., prepend a counter and append a checksum), and then 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 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 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.

Pre-2018 CSE ID: CS2000-0646