Ring learning with errors key exchange: Difference between revisions

Revision as of 18:24, 11 November 2015

Revision as of 18:28, 11 November 2015

Line 24:

# 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+1, -b+2. ... -2, -1, 0, 1, 2, ... , b-2, b-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-5, q-4, q-3, q-2, q-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-1)/2 to (q-1)/2 } according to a discrete Gaussian distribution with mean 0 and distribution parameter σ. 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 = http://www.cc.gatech.edu/~cpeikert/pubs/slides-pargauss.pdf|url = http://www.cc.gatech.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. The maximum degree of the polynomials (n) will be a power of 2. This follows the work of Singh.<ref name=":1" /> Other cases for q and n are thoroughly discussed in "A Toolkit for Ring-LWE Cryptography."<ref name=":2" /> A fixed public polynomial, a(x), shared by all users of the network. It is deterministically generated from a cryptographically secure source. In November 2015, Alkim, Ducas, Popplemann, and Schwabe built on the prior work of Peikert and Singh and used what they believe is a more precise costing of lattice attacks to recommend parameters somewhat smaller (by 3 bits) than those recommended by Singh.<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><ref name=":1" /> They also introduce a different reconciliation mechanism than Peikert and Singh.

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 t(x) = a(x)s(x) + e(x). The security of the key exchange that follows is based the difficulty of finding a pair of small polynomials s'(x) and e'(x) such that for a given t(x), a(x)s'(x) + e'(x) = t(x).

Line 76:

==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" /> Software based on the work of Alkim, Ducas, Popplemann, and Schwabe is found on GitHub at https://github.com/tpoeppelmann/newhope<ref name=":3" /> The preceding software packages closely follow the work of Peikert.<ref name=":0" /> However, the software by Poppelmann implements the new techniques they introduced in their 2015 paper including transmission of extra information over the channel to allow for random generation of a polynomial "base point" for the key exchange<ref name=":3" />

== Other approaches ==

A variant of the approach described above but with very different reconciliation function and parameter choices is 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 = http://www.nist.gov/itl/csd/ct/post-quantum-crypto-workshop-2015.cfm|website = www.nist.gov|accessdate = 2015-06-06}}</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 = https://pqc2010.cased.de/rr/03.pdf|url = https://pqc2010.cased.de/rr/03.pdf|website = pqc2010.cased.de|accessdate = 2015-06-06}}</ref> This work was then extended and put on a much more rigorous foundation by Peikert in his writings.<ref name=":0" /><ref name=":2">{{Cite journal|title = A Toolkit for Ring-LWE Cryptography|url = http://eprint.iacr.org/2013/293|date = 2013|first = Vadim|last = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev}}</ref>

In November 2015, Alkim, Ducas, Popplemann, and Schwabe built on the prior work of Peikert and Singh and used what they believe is a more precise costing of lattice attacks to recommend parameters somewhat smaller (by 3 bits) than those recommended by Singh.<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><ref name=":1" /> They also introduce a different reconciliation mechanism and security proof than that used by Peikert and Singh. Software based on the work of Alkim, Ducas, Popplemann, and Schwabe is found on GitHub at https://github.com/tpoeppelmann/newhope<ref name=":3" />

== See also ==