Cryptology ePrint Archive: Report 2014/426

Efficient Authentication and Pseudorandomness from Weaker (Ring-)LPN Assumptions

Ivan Damg{\aa}rd and Sunoo Park and Sarah Zakarias

Abstract: We propose a two new approaches to authentication based on the (ring-)LPN problem. In contrast to all known approaches, we can use a noise rate for the LPN problem that is arbitrarily close to 1/2, without this affecting the communication complexity of the protocol, and while doing only (poly-)logarithmic depth computation. At the cost of having the prover keep a small amount of state, our approach allows us to ``upgrade'' the HB protocol from passive to the man-in-the-middle security (the strongest notion) while maintaining its simple structure.

A technical contribution of independent interest is a construction of a poly-logarithmic depth PRF from LPN that is secure if at most a predetermined number $\ell$ of queries are asked; if more queries are asked, the same PRF is still secure, but now under a stronger assumption closely related to LPN. The basic idea of the construction also applies to other problems with a similar structure, such as subset-sum.

Category / Keywords: cryptographic protocols / LPN, ring-LPN, authentication, identification, pseudorandom functions

Date: received 4 Jun 2014

Contact author: sunoo at csail mit edu

Available format(s): PDF | BibTeX Citation

Version: 20140606:141503 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]