The learning with errors (LWE) problem asks to distinguish "noisy"
inner products of a secret vector with random vectors from uniform. The LWE problem has found many applications in cryptography.
In this talk I will first introduce a (seemingly) much stronger "interactive" assumption called subspace LWE, but which can be proven to be equivalent to the original LWE problem.
This implies directly that the LWE problem is surprisingly robust with respect to tampering with the secret and/or the randomness used to generate the samples. This robustness translates to stronger security guarantees (e.g. it implies security against a broad class of related-key attacks) one can give for cryptosystems proven secure under the standard LWE assumption.
In the second part of the talk I'll show simple and extremely efficient constructions of authentication protocols and message authentication codes (MACs) whose security can be reduced to subspace LPN.
This talk is partially based on the paper "Efficient Authentication from Hard Learning Problems" (with Eike Klitz, David Cash, Abhishek Jain and Daniele Venturi. To appear at Eurocrypt 2011.)
Copyright. All Rights Reserved.