[Resource Topic] 2002/132: Tight Lower Bound on Linear Authenticated Encryption

Welcome to the resource topic for 2002/132

Tight Lower Bound on Linear Authenticated Encryption

Authors: Charanjit S. Jutla


We show that any scheme
to encrypt m blocks of size n bits while assuring
message integrity,
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.

ePrint: https://eprint.iacr.org/2002/132

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .