Cryptology ePrint Archive: Report 2002/132
Tight Lower Bound on Linear Authenticated Encryption
Charanjit S. Jutla
Abstract: We show that any scheme
to encrypt m blocks of size n bits while assuring
apart from using m+k invocations of
random functions (from n bits
to n bits) and vn bits of randomness, is linear in (GF2)^n,
must have k+v at least Omega(log m).
This lower bound is proved in a very general model which rules
out many promising linear modes of operations for encryption
with message integrity.
This lower bound is
tight as linear
schemes to encrypt m blocks while
assuring message integrity by using only m+2+log m invocations
of random permutations.
Category / Keywords: secret-key cryptography / encryption, authentication, block cipher, MAC, lower bound
Date: received 28 Aug 2002
Contact author: csjutla at watson ibm com
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Version: 20020828:201803 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]