Content deleted Content added
Carvalho1988 (talk | contribs) Added other approaches section to demonstrate that there are other approaches to a Ring LWE key exchange than the one outlined in the article. |
Carvalho1988 (talk | contribs) m Cleaned up grammar |
||
Line 5:
----
{{technical|date=June 2015}}[[Cryptography]] is the art and science of secret writing; the task of transmitting secret messages through insecure channels in a manner such that no one but the intended recipient can read the transmitted message. In the 20th century, [[cryptography]] has become the subject of intense interest by governments, companies, and individuals eager to send and receive secret messages over vast communications networks spanning the globe. It involves the mathematics of taking computer generated bit streams which encode information and transforming them using a computer algorithm and a [[secret key]] (a relatively short secret of bits) into encrypted information. The encrypted information is sent over a communications channel to an intended recipient. If the intended recipient has the same secret key and the same computer algorithm, they can transform the encrypted information back into it's original state (plaintext). This article is about one way a sender and intended recipient can create a secret key that they both share.
This article is about a special set cryptographic [[computer algorithms]] called public [[key exchange]] algorithms. In these algorithms a sender and a recipient each generate random information and combine this information with fixed and known information to form a public key. The sender and recipient then exchange public keys. Each party then uses the received public key and their random information in an algorithm to produce what is generally called a shared secret. The classic example of a key exchange is something known as the [[Diffie–Hellman key exchange|Diffie-Hellman key exchange]]. This article discusses a different key exchange that has many of the same properties as the [[Diffie–Hellman key exchange|Diffie-Hellman key exchange]]. See the link on Diffie-Hellman for more information on it.
The motivation for this different key exchange and for this article is the ability of a quantum computer to break the key exchange algorithms used today to secure the internet. Whether its logging on to a social media site or remotely connecting to an office over the internet some for of public key exchange is used. A [[Quantum computing|quantum computer]], if it can be built, will render the currently used algorithms insecure. This article is about one approach to remedy this problem and protect internet security from potential advances in quantum computers.
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 [[Polynomial ring|Ring of Polynomials]] over a [[Finite field|Finite Field]]. This specialized 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 cryptography|public key encryption]] algorithms, [[homomorphic encryption]] algorithms, and [[Digital Signature Algorithm|digital
A [[key exchange algorithm]] is a type of public key algorithm which establishes a shared secret key between to communicants on a communications link. The classic example of a key exchange is the [[Diffie–Hellman key exchange|Diffie-Hellman]] key exchange. The exchange consists of one transmission from one end of the line and one transmission from the other end of the link. [[Diffie–Hellman key exchange|Diffie-Hellman]] and [[Elliptic curve Diffie–Hellman|Elliptic Curve Diffie-Hellman]] are the two most popular key exchange algorithms.
Line 35:
=== 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 responder designated as (R). Both I and R know, q, n, a(x), and have the ability to generate small polynomials according to the distribution '''D'''. The description which follows does not contain any explanation of why the key exchange results in the same key at both ends of a link. Rather it succinctly specifies the steps to be taken. For
The key exchange begins with the initiator (I) doing the following:
Line 76:
For 256 bits of security, n = 1024, q = 40961, and F(x) = x<sup>1024</sup> + 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<sup>-71</sup> for the 128-bit secure parameters and <u>less than</u> 2<sup>-91</sup> for the 256-bit secure parameters.
=== Key Exchange Security ===
| |||