Cryptology ePrint Archive: Report 2012/688
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem
Jintai Ding, Xiang Xie, Xiaodong Lin
Abstract: We use the learning with errors (LWE) problem to build a new simple and provably secure key exchange scheme. The basic idea of
the construction can be viewed as certain extension of Diffie-Hellman problem with errors. The mathematical structure behind comes from the commutativity of computing a bilinear form in two different ways due to the associativity of the matrix multiplications:$$(X^t \times A)\times Y=X^t \times (A\times Y),$$ where
$X,Y$ are column vectors and $A$ is a square matrix. We show that our new schemes are more efficient in terms of communication complexity and computation
complexity compared with key exchange schemes or key transport schemes via encryption schemes based on the LWE problem.
Furthermore, we extend our scheme to the ring learning with errors (RLWE) problem, resulting in small key size and better efficiency.
Category / Keywords: Key Exchange, LWE, bilinear form, provable security
Date: received 9 Dec 2012, last revised 23 Mar 2014
Contact author: jintai ding at gmail com
Available format(s): PDF | BibTeX Citation
Note: The security proof is added and this version of the paper was submitted to Eurocrypt 2014.
Version: 20140324:022102 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]