IACR News item: 06 June 2014
Ivan Damg{\\aa}rd, Sunoo Park, Sarah Zakarias
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.
Additional news items may be found on the IACR news page.