Cryptology ePrint Archive: Report 2015/324

A Note on Lower Bounds for Non-interactive Message Authentication Using Weak Keys

Divesh Aggarwal and Alexander Golovnev

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

Category / Keywords: foundations / message authentication codes; weak keys; entropy; hash functions

Original Publication (with minor differences): 2015 IEEE Information Theory Workshop

Date: received 9 Apr 2015, last revised 7 Aug 2015

Contact author: alexgolovnev at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150807:124705 (All versions of this report)

Short URL: ia.cr/2015/324

Discussion forum: Show discussion | Start new discussion