TY - CONF AB - We construct efficient authentication protocols and message-authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work - starting with the HB protocol of Hopper and Blum in 2001 - until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle (MIM) attacks. A MAC implies such a (two-round) protocol. © 2011 International Association for Cryptologic Research AU - Kiltz, Eike AU - Pietrzak, Krzysztof Z AU - Cash, David AU - Jain, Abhishek AU - Venturi, Daniele ID - 3238 TI - Efficient authentication from hard learning problems VL - 6632 ER -