Content deleted Content added
m task, replaced: Thirty-seventh → Thirty-Seventh (2) |
Citation bot (talk | contribs) Alter: template type. Add: journal. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 471/3850 |
||
Line 19:
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|year=2012}}</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|journal=Cryptology ePrint Archive |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.
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|journal=Cryptology ePrint Archive |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|journal=Cryptology ePrint Archive |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|year=2012}}</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 32:
# 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 = An Efficient and Parallel Gaussian Sampler for Lattices|url = https://web.eecs.umich.edu/~cpeikert/pubs/slides-pargauss.pdf|website = www.cc.gatech.edu|access-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|journal=Cryptology ePrint Archive |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|first1 = Joppe W.|last1 = Bos|first2 = Craig|last2 = Costello|first3 = Michael|last3 = Naehrig|first4 = Douglas|last4 = Stebila| journal=Cryptology ePrint Archive }}</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
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|access-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" />
| |||