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

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 format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20020828:201803 (All versions of this report)

Short URL: ia.cr/2002/132

Discussion forum: Show discussion | Start new discussion