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
-
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},
url = {https://eprint.iacr.org/2015/324}
}
