International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 06 June 2014

Ivan Damg{\\aa}rd, Sunoo Park, Sarah Zakarias
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.