Ring learning with errors key exchange: Difference between revisions

Revision as of 00:24, 30 January 2019

Revision as of 02:12, 21 February 2019

Line 17:

Starting with a [[Prime number|prime]] integer q, the [[fing learning with errors|Ring-LWE]] key exchange works in the [[ring of polynomials]] modulo a polynomial <math>\Phi(x)</math> 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 <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 14,000 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:

: <math> a(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-3} x^{n-3} + a_{n-2} x^{n-2} + a_{n-1} x^{n-1} </math>

Line 26:

# Using [[Uniform distribution (discrete)|Uniform Sampling]] – The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let ''b'' be an integer that is much less than ''q''. If we randomly choose coefficients from the set: { −''b'', −b&nbsp;+&nbsp;1, −b&nbsp;+&nbsp;2. ... −2, −1, 0, 1, 2, ... , ''b''&nbsp;−&nbsp;2, ''b''&nbsp;−&nbsp;1, ''b''} the polynomial will be small with respect to the bound (b). Singh suggest using b = 5.<ref name=":1" /> Thus coefficients would be chosen from the set {''q''&nbsp;−&nbsp;5, ''q''&nbsp;−&nbsp;4, ''q''&nbsp;−&nbsp;3, ''q''&nbsp;−&nbsp;2, ''q''&nbsp;−&nbsp;1, 0, 1, 2, 3, 4, 5 }.

# Using [[Gaussian distribution|Discrete Gaussian]] Sampling – For an odd value for q, the coefficients are randomly chosen by sampling from the set { −(q&nbsp;−&nbsp;1)/2 to (''q''&nsbp;−&nbsp;1)/2 } according to a discrete Gaussian distribution with mean 0 and distribution parameter&nbsp;''σ''. The references describe in full detail how this can be accomplished. It is more complicated than uniform sampling but it allows for a proof of security of the algorithm. An overview of Gaussian sampling is found in a presentation by Peikert.<ref>{{Cite web|title = An Efficient and Parallel Gaussian Sampler for Lattices|url = https://web.eecs.umich.edu/~cpeikert/pubs/slides-pargauss.pdf|website = www.cc.gatech.edu|accessdate = 2015-05-29}}</ref>

For the rest of this article, the random small polynomials will be sampled according to a distribution which is simply specified as '''D'''. Further q will be an odd prime such that q is congruent to 1 mod 4 and 1 mod 2n. Other cases for q and n are thoroughly discussed in "A Toolkit for Ring-LWE Cryptography" and in Singh's "Even More Practical Key Exchange for the Internet using Lattice Cryptography."<ref name=":2">{{Cite journal|last=Lyubashevsky|first=Vadim|last2=Peikert|first2=Chris|last3=Regev|first3=Oded|date=2013|title=A Toolkit for Ring-LWE Cryptography|url=http://eprint.iacr.org/2013/293}}</ref><ref>{{Cite web|title = Cryptology ePrint Archive: Report 2015/1120|url = http://eprint.iacr.org/2015/1120|website = eprint.iacr.org|access-date = 2016-01-17}}</ref> and another paper by Singh. A fixed public polynomial, a(x), shared by all users of the network. It is deterministically generated from a cryptographically secure source.

Given ''a''(''x'') as stated, we can randomly choose small polynomials ''s''(''x'') and ''e''(''x'') to be the "private key" in a public key exchange. The corresponding public key will be the polynomial ''p''(''x'') = ''a''(''x'')''s''(''x'') + 2''e''(''x'').

Line 92:

==Implementations==

In 2014 Douglas Stebila made [http://www.douglas.stebila.ca/research/papers/bcns15 a patch] for OpenSSL 1.0.1f. based on his work and others published in "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem."<ref>{{Cite journal|title = Post-quantum key exchange for the TLS protocol from the ring learning with errors problem|url = http://eprint.iacr.org/2014/599|date = 2014-01-01|first = Joppe W.|last = Bos|first2 = Craig|last2 = Costello|first3 = Michael|last3 = Naehrig|first4 = Douglas|last4 = Stebila}}</ref> Software implementing the work of Singh is found on GitHub at [https://github.com/vscrypto/ringlwe https://github.com/vscrypto/ringlwe.]<ref name=":1" />

== Other approaches ==

A variant of the approach described above is an authenticated version in the work of Zhang, Zhang, Ding, Snook and Dagdelen in their paper, "Post Quantum Authenticated Key Exchange from Ideal Lattices."<ref>{{Cite web|title = Workshop on Cybersecurity in a Post-Quantum World|url = https://www.nist.gov/itl/csd/ct/post-quantum-crypto-workshop-2015.cfm|website = www.nist.gov|accessdate = 2015-06-06|date = 2015-04-02}}</ref> The concept of creating what has been called a Diffie–Hellman-like Key Exchange using lattices with a reconciliation function appears to have first been presented by French researchers Aguilar, Gaborit, Lacharme, Schrek, and Zemor at PQCrypto 2010 in their talk, "Noisy Diffie–Hellman Protocols."<ref>{{Cite web|title = Noisy Diffie–Hellman protocols|url = https://pqc2010.cased.de/rr/03.pdf|website = pqc2010.cased.de|accessdate = 2015-06-06}}</ref>

In November 2015, Alkim, Ducas, Popplemann, and Schwabe built on the prior work of Peikert and used what they believe is a more conservative costing of lattice attacks to recommend parameters.<ref name=":3">{{Cite web|title = Cryptology ePrint Archive: Report 2015/1092|url = https://eprint.iacr.org/2015/1092|website = eprint.iacr.org|accessdate = 2015-11-11}}</ref> Software based on the work of Alkim, Ducas, Popplemann, and Schwabe is found on GitHub at https://github.com/tpoeppelmann/newhope<ref name=":3" />