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

Jintai Ding, Xiang Xie, and 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:$$(\mathbf{x}^t \times \mathbf{A})\times \mathbf{y}=\mathbf{x}^t \times (\mathbf{A}\times \mathbf{y}),$$ where $\mathbf{x,y}$ are column vectors and $\mathbf{A}$ is a square matrix. We show that our new schemes are more efficient in terms of communication 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.

Note: The security proof is added and this version of the paper was submitted to Eurocrypt 2014.

Available format(s)
Publication info
Published elsewhere. Unknown status
Keywords
Key ExchangeDiffie-HellmannLWE
Contact author(s)
jintai ding @ gmail com
History
2014-07-29: last of 4 revisions
See all versions
Short URL
https://ia.cr/2012/688

CC BY

BibTeX

@misc{cryptoeprint:2012/688,
author = {Jintai Ding and Xiang Xie and Xiaodong Lin},
title = {A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem},
howpublished = {Cryptology ePrint Archive, Paper 2012/688},
year = {2012},
note = {\url{https://eprint.iacr.org/2012/688}},
url = {https://eprint.iacr.org/2012/688}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.