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


The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego, techreports@cs.ucsd.edu.


[ Search ]


NCSTRL
This server operates at UCSD Computer Science and Engineering.
Send email to webmaster@cs.ucsd.edu