A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem

The authors use a variant of Learning With Errors (LWE) problem, a simple and direct extension of the original LWE problem to the case of a small secret, which they call a Small LWE problem (SLWE), to build a new simple and provably secure key exchange scheme. The basic idea behind the construction can be viewed as certain type of bilinear Pairing with Errors (PE). They build a more efficient implementation of their scheme using a similar LWE problem but solely based on matrices, and they extend their construction further using the ring LWE problem, where the provable security is based on the hardness of the ring LWE problem.

Resource Details

Provided by:
University of Chile