Paper 2014/426

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

Ivan Damgå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.