Title: Efficient Authentication from the Learning Parity with Noise Problem
Speaker: David Cash, Rutgers University
Date: Wednesday, November 28, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk I will describe new constructions of authentication protocols and message authentication codes (MACs) from the learning parity with noise (LPN) problem. The LPN problem provides an attractive basis for cryptography as it is equivalent to the well-studied problem of decoding random linear codes and, unlike most number-theoretic cryptographic problems, has no known weakness to quantum attacks. Moreover, its simple structure suggests that it can be used to build highly efficient algorithms.
Our constructions give the most efficient LPN-based authentication protocols and MACs to date, and our techniques depart significantly from the relatively large body of work on this subject. Our security proofs hinge upon a new technical result, which may have further applications, where we show that the LPN problem remains hard under a strong, adaptive type of secret-tampering.
This work is joint with Eike Kiltz, Krzysztof Pietrzak, Abhishek Jain, and Daniele Venturi.