International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Tight Lower Bound on Linear Authenticated Encryption

Authors:
Charanjit S. Jutla
Download:
URL: http://eprint.iacr.org/2002/132
Search ePrint
Search Google
Abstract: We show that any scheme to encrypt m blocks of size n bits while assuring message integrity, that 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 are known. of random permutations.
BibTeX
@misc{eprint-2002-11655,
  title={Tight Lower Bound on Linear Authenticated Encryption},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / encryption, authentication, block cipher, MAC, lower bound},
  url={http://eprint.iacr.org/2002/132},
  note={ csjutla@watson.ibm.com 11927 received 28 Aug 2002},
  author={Charanjit S. Jutla},
  year=2002
}