Content deleted Content added
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 |
→The key exchange: fixed typo Z_a not Zq Tags: Mobile edit Mobile web edit |
||
| (6 intermediate revisions by 5 users not shown) | |||
Line 6:
Since the 1980s the security of cryptographic [[key exchange]]s and [[digital signature]]s over the Internet has been primarily based on a small number of [[public key]] algorithms. The security of these algorithms is based on a similarly small number of computationally hard problems in classical computing. These problems are the difficulty of [[Integer factorization|factoring the product of two carefully chosen prime numbers]], the difficulty to compute [[discrete logarithms]] in a carefully chosen finite field, and the difficulty of computing discrete logarithms in a carefully chosen [[elliptic curve]] group. These problems are very difficult to solve on a classical computer (the type of computer the world has known since the 1940s through today) but are rather easily solved by a relatively small [[Quantum computing|quantum computer]] using only 5 to 10 thousand of bits of memory. There is optimism in the computer industry that larger scale quantum computers will be available around 2030. If a [[quantum computer]] of sufficient size were built, all of the public key algorithms based on these three classically hard problems would be insecure. This public key cryptography is used today to secure Internet websites, protect computer login information, and prevent our computers from accepting malicious software.
Cryptography that is not susceptible to attack by a quantum computer is referred to as [[post-quantum cryptography|quantum safe]], or [[post-quantum cryptography]]. One class of quantum resistant cryptographic algorithms is based on a concept called "[[learning with errors]]" introduced by [[Oded Regev (computer scientist)|Oded Regev]] in 2005.<ref name=":4">{{Cite book
There are a variety of cryptographic algorithms which work using the RLWE paradigm. There are [[Public-key cryptography|public-key encryption]] algorithms, [[homomorphic encryption]] algorithms, and [[Ring learning with errors signature|RLWE digital signature]] algorithms in addition to the public key, key exchange algorithm presented in this article
Line 21:
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 "
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:
Line 27:
: <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 <math>a_i</math> of this polynomial
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'' − 1)/2,..., 0, ... (''q'' − 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<sub>n-1</sub>, ..., s<sub>0</sub>) which are guaranteed or very likely to be small. There are two common ways to do this:
Line 37:
== The key exchange ==
The key exchange will take place between two devices. There will be an initiator for the key exchange designated as (I) and a respondent designated as (R). Both I and R know ''q'', ''n'', ''a''(''x''), and have the ability to generate small polynomials according to the distribution <math>\chi_\alpha</math> with parameter <math>\alpha</math>. The distribution <math>\chi_\alpha</math> is usually the discrete Gaussian distribution on the ring <math> R_q =
The key exchange begins with the initiator (I) doing the following:
Line 86:
In their November 2015 paper, Alkim, Ducas, Pöppelmann, and Schwabe recommend the following parameters n = 1024, q =12289, and <math>\Phi(x)</math> = x<sup>1024</sup> + 1.<ref name=":3" /> This represents a 70% reduction in public key size over the n = 1024 parameters of Singh, and was submitted to NIST's [[Post-Quantum Cryptography Standardization]] project under the name [[NewHope]].
Also in their November 2015 paper, Alkim, Ducas, Pöppelmann and Schwabe recommend that the choice of the base polynomial for the key exchange ( a(x) above ) be either generated randomly from a secure random number generator for each exchange or created in a verifiable fashion using a "nothing up my sleeve" or NUMS technique.<ref name=":3" /> An example of parameters generated in this way are the prime numbers for the Internet Key Exchange (<nowiki>RFC 2409</nowiki>) which embed the digits of the mathematical constant pi in the digital representation of the prime number.<ref>{{Cite
== Key exchange security ==
The security of this key exchange is based on the underlying hardness of [[ring learning with errors]] problem that has been proven to be as hard as the worst case solution to the [[shortest vector problem]] (SVP) in an [[ideal lattice cryptography|ideal lattice]].<ref name=":4" /><ref name=":0" /> The best method to gauge the practical security of a given set of lattice parameters is the BKZ 2.0 lattice reduction algorithm.<ref>{{Cite book
==Implementations==
Line 95:
== 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 journal|title = Workshop on Cybersecurity in a Post-Quantum World|url = https://www.nist.gov/itl/csd/ct/post-quantum-crypto-workshop-2015.cfm|journal =
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" />
Line 108:
== References ==
{{reflist}}
==External links==
{{ Cryptography navbox | public-key }}
[[Category:Cryptographic algorithms]]
| |||