International Association
for Cryptologic Research

In this note, we prove lower bounds on the amount of entropy of random sources necessary for secure message authentication. We consider the problem of non-interactive c-time message authentication using a weak secret key having min-entropy k. We show that existing constructions using (c+1)-wise independent hash functions are optimal.

This result resolves one of the main questions left open by the work of Dodis and Spencer [DS02] who considered this problem for one-time message authentication of one-bit messages.