Lapin: An Efficient Authentication Protocol Based on Ring-LPN

The authors propose a new authentication protocol that is provably secure based on a ring variant of the Learning Parity with Noise (LPN) problem. The protocol follows the design principle of the LPN-based protocol from Eurocrypt'11 (Kiltz et al.), and like it, is a two round protocol secure against active attacks. Moreover, their protocol has small communication complexity and a very small footprint which makes it applicable in scenarios that involve low-cost, resource constrained devices. Performance-wise, their protocol is more efficient than previous LPN-based schemes, such as the many variants of the Hopper-Blum (HB) protocol and the aforementioned protocol from Eurocrypt'11.