Paper 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 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.

Metadata
Available format(s)
PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
encryptionauthenticationblock cipherMAClower bound
Contact author(s)
csjutla @ watson ibm com
History
2002-08-28: received
Short URL
https://ia.cr/2002/132
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/132,
      author = {Charanjit S.  Jutla},
      title = {Tight Lower Bound on Linear Authenticated Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2002/132},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/132}},
      url = {https://eprint.iacr.org/2002/132}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.