Towards Optimally Efficient Secret-Key Authentication from PRG

Ivan Damgård; Sunoo Park

Paper 2014/426

Towards Optimally Efficient Secret-Key Authentication from PRG

Ivan Damgård and Sunoo Park

Abstract

We propose a new approach to the construction of secret-key authentication protocols making black-box use of any pseudorandom generator (PRG). Our authentication protocols require only two messages, have perfect completeness, and achieve concurrent man-in-the-middle security. Finally, when based on a sufficiently efficient PRG, our protocol has (amortised) complexity $O (n)$ bit operations where $n$ is the security parameter. To the best of our knowledge, this construction is the first with linear complexity. We achieve this at the cost of having the prover (but not the verifier) keep a small amount of state. A variant of our construction, based on a stronger security notion for the PRG, is secure even if the adversary is able to reset the prover an unbounded number of times. A practical analysis of our protocol shows our prover computation time compares favorably against a simple AES-based protocol.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Authentication pseudorandom generators linear time
Contact author(s): sunoo @ csail mit edu
History: 2016-02-10: last of 5 revisions; 2014-06-06: received; See all versions
Short URL: https://ia.cr/2014/426
License: CC BY

BibTeX

@misc{cryptoeprint:2014/426,
      author = {Ivan Damgård and Sunoo Park},
      title = {Towards Optimally Efficient Secret-Key Authentication from {PRG}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/426},
      year = {2014},
      url = {https://eprint.iacr.org/2014/426}
}