You are looking at a specific version 20150305:095709 of this paper. See the latest version.

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 a 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 to have all these properties simultaneously, in particular 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. Very practical PRGs can be constructed, for instance, based on the Learning Parity with Noise (LPN) problem, and our protocol is in several respects an attractive alternative even to protocols derived directly from LPN. A variant of our construction is secure even if the adversary is able to reset the prover.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Authenticationpseudorandom generatorslinear 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.