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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. 2015 IEEE Information Theory Workshop
Keywords
message authentication codesweak keysentropyhash functions
Contact author(s)
alexgolovnev @ gmail com
History
2015-08-07: revised
2015-04-11: received
See all versions
Short URL
https://ia.cr/2015/324
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/324,
      author = {Divesh Aggarwal and Alexander Golovnev},
      title = {A Note on Lower Bounds for Non-interactive Message Authentication Using Weak Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2015/324},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/324}},
      url = {https://eprint.iacr.org/2015/324}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.