Ring learning with errors key exchange: Difference between revisions

Revision as of 21:13, 30 August 2017

Revision as of 22:27, 6 September 2017

Line 15:

== Introduction ==

Starting with a [[Prime number|prime]] integer q, the [[Ring Learning with Errors|Ring-LWE]] key exchange works in the [[ring of polynomials]] modulo a polynomial <nowiki><math>\Phi(x)</math></nowiki> with coefficients in the field of integers mod q (i.e. the ring <math>R_q := Z_q[x] / \Phi(x)</math>). Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod <nowiki><math>\Phi(x)</math></nowiki><math>\Phi(x)</math>.

In 2014, Peikert<ref>{{Cite journal|last=Peikert|first=Chris|date=2014-01-01|title=Lattice Cryptography for the Internet|url=http://eprint.iacr.org/2014/070|journal=|volume=|issue=|doi=|pmid=|access-date=|via=}}</ref> presented a key transport scheme based on Ring-LWE. For somewhat greater than 128 [[bits of security]], Singh presents a set of parameters which have 6956-bit public keys for the Peikert's scheme.<ref name=":1">{{Cite journal|last=Singh|first=Vikram|date=2015|title=A Practical Key Exchange for the Internet using Lattice Cryptography|url=http://eprint.iacr.org/2015/138}}</ref> The corresponding private key would be roughly 14000 bits. An RLWE version of the classic MQV variant of a Diffie-Hellman key exchange was later published by Zhang et al. in 2014. The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice.This article will closely follow the RLWE work of Ding in "A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem".<ref name=":0">{{Cite book|url=https://eprint.iacr.org/2012/688.pdf|title=A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem|last=Ding|first=Jintai|last2=Xie|first2=Xiang|last3=Lin|first3=Xiaodong|publisher=|year=2012|isbn=|___location=|pages=|via=}}</ref> For this presentation a typical polynomial is expressed as: