Ring learning with errors key exchange: Difference between revisions

Revision as of 02:42, 4 June 2015

Revision as of 01:21, 6 June 2015

Line 14:

Since the 1980's 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. A quantum computer would undermine the security of these functions and of electronic commerce and data exchange in general.

Cryptography that is not susceptible to attack by a quantum computer is referred to as [[Post-quantum cryptography|Quantum Resistant]], [[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>{{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 Ring of Polynomials over a Finite Field. This specialisedspecialized form is called Ring Learning with Errors or [[Ideal lattice cryptography|Ring-LWE]].

There are a variety of cryptographic algorithms which work using the Ring-LWE paradigm. There are public key encryption algorithms, [[homomorphic encryption]] algorithms, and digital signatures in addition to the public key, key exchange algorithm presented in this article

Line 76:

For 256 bits of security, n = 1024, q = 40961, and F(x) = x¹⁰²⁴ + 1

Because the key exchange uses random sampling and fixed bounds there is a small probability that the key exchange will fail to produce the same key for the initiator and responder. If we assume that the gaussian parameter σ is 8/sqrt(2π) and the uniform sampling bound (b) = 5 (see Singh)<ref name=":1" />, then the probability of key agreement failure is <u>less than</u> 2^-71 for the 128-bit secure parameters and less than 2^-91 for the 256-bit secure parameters.

=== Key Exchange Security ===