Cryptology ePrint Archive: Report 2014/426

Efficient Authentication from PRG, Revisited

Ivan Damg{\aa}rd and Sunoo Park

Abstract: We propose a new approach to the construction of secret-key authentication protocols from pseudorandom generators (PRG). Our authentication protocols require only two messages, have perfect completeness, and achieve the strongest meaningful security notion (man-in-the-middle security). Finally, if the PRG can be computed in poly-logarithmic depth, the authentication protocol also requires only poly-logarithmic depth computation. To the best of our knowledge, this construction is the first to have all these properties simultaneously. We achieve this at the cost of having the prover (but not the verifier) keep a small amount of state. Very efficient PRGs that can be computed in small depth 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 that are derived directly from LPN. A variant of our construction is secure even if the adversary is able to reset the prover.

Category / Keywords: Authentication, pseudorandom generators, pseudorandom functions, LPN

Date: received 4 Jun 2014, last revised 20 Oct 2014

Contact author: sunoo at csail mit edu

Available format(s): PDF | BibTeX Citation

Version: 20141021:031013 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]