Ring learning with errors key exchange: Difference between revisions

Revision as of 22:25, 13 June 2015

Revision as of 15:27, 14 June 2015

Line 1:

{{Multiple issues|

{{technical|date=June 2015}}

{{Orphan|date=June 2015}}

}}

In [[cryptography]], a [[key exchange|public key exchange]] is a [[cryptographic algorithm]] which allows two parties to create and share a secret key which they use to encrypt messages between themselves. The Ring Learning with Errors Key Exchange (RLWE-KEX) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a [[quantum computer]]. This is important because all of the [[public key algorithm|public key algorithms]]s in use today are easily broken by a quantum computer and scientists are making steady progress toward creating such a computer. The RLWE-KEX is one of a set of [[Post-quantum cryptography|Post Quantum cryptographic]] algorithms being which are based on the difficulty of solving mathematical certain mathematical problems involving [[Lattice-based cryptography|lattices]]. Unlike older lattice based cryptographic algorithms, the RLWE-KEX is provably reducible to a known hard problem in lattices.

== Background ==

Since the 1980s the security of cryptographic [[key exchange]]<nowiki/>s and [[digital signature]]<nowiki/>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 1940's 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. As of 2015 no one has built a quantum computer with even 50-bits of memory but there is optimism in the computer industry that larger scale quantum computers will be available in the next 15 years. If a [[quantum computer]] of sufficient size were built, all of the public key algorithms based on these three classically hard problems would become extremely 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|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>{{Cite journal|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 = 1-58113-960-8|pages = 84–93|series = STOC '05|doi = 10.1145/1060590.1060603|first = Oded|last = Regev}}</ref> A specialized form of Learning with errors operates within the [[Polynomial ring|Ring of Polynomials]] over a [[Finite field|Finite Field]]. This specialized form is called Ring Learning with Errors or [[Ideal lattice cryptography|RLWE]].