Cryptology ePrint Archive: Report 2012/688

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

Jintai Ding, Xiaodong Lin

Abstract: We 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 we 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). We build a more efficient implementation of our scheme using a similar LWE problem but solely based on matrices, and we extend our construction further using the ring LWE problem, where the provable security is based on the hardness of the ring LWE problem.

Category / Keywords: public-key cryptography /

Date: received 9 Dec 2012, last revised 3 Mar 2013

Contact author: jintai ding at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20130303:142813 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]