Ring learning with errors key exchange: Difference between revisions

Revision as of 18:35, 12 January 2019

Revision as of 00:24, 30 January 2019

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]] in 2005.<ref name=":4">{{Cite journalbook|title = On Lattices, Learning with Errors, Random Linear Codes, and Cryptography|url = http://doi.acm.org/10.1145/1060590.1060603|publisher = ACM|journal = Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing|date = 2005|___location = New York, NY, USA|isbn = 978-1-58113-960-80|pages = 84–93|series = STOC '05|doi = 10.1145/1060590.1060603|first = Oded|last = Regev|citeseerx = 10.1.1.110.4776}}</ref> A specialized form of Learning with errors operates within the [[polynomial ring|ring of polynomials]] over a [[finite field]]. This specialized form is called [[ring learning with errors]] or [[ideal lattice cryptography|RLWE]].

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 86:

}}</ref>

Also in their November 2015 paper, Alkim, Ducas, Popplemann 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 web|url=https://tools.ietf.org/html/rfc2409|title=The Internet Key Exchange (IKE)|last=D.|first=Carrel,|last2=D.|first2=Harkins,|website=tools.ietf.org|language=en|access-date=2017-03-16}}</ref> Their first method prevents amortization of attack costs across many key exchanges at the risk of leaving open the possibility of a hidden attack like that described by Dan Bernstein against the NIST elliptic curves.<ref>{{Cite web|url=http://crypto.stackexchange.com/questions/35488/is-the-new-hope-lattice-key-exchange-vulnerable-to-a-lattice-analog-of-the-ber|title=Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?|website=crypto.stackexchange.com|access-date=2017-03-16}}</ref> The NUMS approach is open to amortization but generally avoids the Bernstein attack if only common mathematical constants such as pi and e are used.

== 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|title = BKZ 2.0: Better Lattice Security Estimates|url = https://link.springer.com/chapter/10.1007/978-3-642-25385-0_1|publisher = Springer Berlin Heidelberg|date = 2011|isbn = 978-3-642-25384-3|pages = 1–20|series = Lecture Notes in Computer Science|first = Yuanmi|last = Chen|first2 = Phong Q.|last2 = Nguyen|editor-first = Dong Hoon|editor-last = Lee|editor-first2 = Xiaoyun|editor-last2 = Wang|doi = 10.1007/978-3-642-25385-0_1}}</ref> According to the BKZ 2.0 algorithm the key exchange parameters listed above will provide greater than 128 or 256 bits of security, respectively.

==Implementations==