Ring learning with errors key exchange: Difference between revisions

Revision as of 11:59, 10 December 2020

Revision as of 13:06, 17 December 2020

Line 17:

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 <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>.

The idea of using LWE and Ring LWE for key exchange was first proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper<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|last1=Ding|first1=Jintai|last2=Xie|first2=Xiang|last3=Lin|first3=Xiaodong|publisher=|year=2012|isbn=|___location=|pages=|via=}}</ref> appeared in 2012 after a provisional patent application was filed in 2012. The security of the protocol is proven based on the hardness of solving the LWE problem.

In 2014, Peikert presented a key-transport scheme<ref>{{Cite journal|last=Peikert|first=Chris|date=2014-01-01|title=Lattice Cryptography for the Internet|url=https://eprint.iacr.org/2014/070}}</ref> following the same basic idea of Ding's, where the new idea of sending an additional 1-bit signal for rounding in Ding's construction is also used.

Line 23:

The "new hope" implementation<ref>{{Cite journal|last1=Alkim|first1=Erdem|last2=Ducas|first2=Léo|last3=Pöppelmann|first3=Thomas|last4=Schwabe|first4=Peter|date=2015-01-01|title=Post-quantum key exchange - a new hope|url=https://eprint.iacr.org/2015/1092}}</ref> selected for Google's post-quantum experiment,<ref>{{Cite news|url=https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html|title=Experimenting with Post-Quantum Cryptography|newspaper=Google Online Security Blog|access-date=2017-02-08|language=en-US}}</ref> uses Peikert's scheme with variation in the error distribution.

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|last1=Ding|first1=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>

The coefficients of this polynomial, the ''a''_''i''s, are integers&nbsp;mod&nbsp;''q''. The polynomial <math>\Phi(x)</math> will be the [[cyclotomic polynomial]]. When ''n'' is a power of 2 then <math>\Phi(x) = x^n +1.</math><ref name=":1" /><ref>{{Cite web|title = Cryptology ePrint Archive: Report 2015/1120|url = https://eprint.iacr.org/2015/1120|website = eprint.iacr.org|accessdateaccess-date = 2015-12-23}}</ref>

The RLWE-KEX uses polynomials which are considered "small" with respect to a measure called the "[[infinity norm]]." The infinity norm for a polynomial is simply the value of the largest coefficient of the polynomial when the coefficients are considered as integers in '''Z''' rather than <math>Zq</math> (i.e.from the set {−(''q''&nbsp;−&nbsp;1)/2,..., 0, ... (''q''&nbsp;−&nbsp;1)/2} ). The algorithm's security depends on an ability to generate random polynomials which are small with respect to the infinity norm. This is done simply by randomly generating the coefficients for a polynomial (s_n-1, ..., s₀) which are guaranteed or very likely to be small. There are two common ways to do this:

# 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''&nbsp;−&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|accessdateaccess-date = 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|last1=Lyubashevsky|first1=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.

Line 96:

== 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|accessdateaccess-date = 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|accessdateaccess-date = 2015-06-06}}</ref>

In November 2015, Alkim, Ducas, Pöppelmann, 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|accessdateaccess-date = 2015-11-11}}</ref> Software based on the work of Alkim, Ducas, Pöppelmann, and Schwabe is found on GitHub at https://github.com/tpoeppelmann/newhope<ref name=":3" />

== See also ==