Ring learning with errors key exchange: Difference between revisions

Revision as of 00:52, 30 May 2015

Revision as of 19:45, 30 May 2015

Line 1:

{{AFC submission|||ts=20150517232922|u=Carvalho1988|ns=118}}

=== Background ===

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 but are rather easily solved by a relatively small [[Quantum computing|quantum computer]]. If a [[quantum computer]] of sufficient size were buildbuilt, all of the public key algorithms based on these three classically hard problems would become extremely insecure.

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 specialised form is called Ring Learning with Errors or [[Ideal lattice cryptography|Ring-LWE]].

Line 9:

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.

The Ring-LWE Key Exchange is designed to be a "quantum safe" replacement for the widely used [[Diffie-Hellman]] and [[Elliptic Curve Diffie-Hellman]] key exchanges that are used to secure the establishment of secret keys over untrusted communications channels. Like Diffie-Hellman and Elliptic Curve Diffie-Hellman, the Ring-LWE key exchange presented in this article provides a cryptographic property called "[[forward secrecy]]"; the aim of which is to reduce the effectiveness of mass surveillance programs and ensure that there are no long term secret keys that can be compromised that would enable bulk decryption.

=== Introduction ===

ForStarting anwith a prime integer, nq, the Ring-LWE key exchange works in the ring of polynomials modulo a polynomial g(x) with coefficients in the field of integers mod q, F_q. (i.e. the ring F_q[x]/g(x) ). Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod g(x). This article will closely follow the Ring-LWE work of Peikert in "Lattice Cryptography for the Internet" as further explained by Singh <ref name=":0">{{Cite book|title = Lattice Cryptography for the Internet|url = http://link.springer.com/chapter/10.1007/978-3-319-11659-4_12|publisher = Springer International Publishing|date = 2014|isbn = 978-3-319-11658-7|pages = 197-219|series = Lecture Notes in Computer Science|language = en|first = Chris|last = Peikert|editor-first = Michele|editor-last = Mosca}}</ref><ref name=":1">{{Cite journal|title = A Practical Key Exchange for the Internet using Lattice Cryptography|url = http://eprint.iacr.org/2015/138|date = 2015|first = Vikram|last = Singh}}</ref>. For this presentation a typical polynomial is expressed as:

a(x) = a₀ + a₁x + a₂x² + ... + a_n-3x^n-3 + a_n-2x^n-2 + a_n-1x^n-1

The coefficients of this polynomial, the a_i's, are integers mod q where q is a prime number.

The Ring-LWE key exchange 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 vice Z/qZ). The algorithm's security will depend 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_n-1, ..., s₀) which are guaranteed or very likely to be small. There are two common ways to do this:

# Using Uniform Sampling - The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let b be an integer that is much less than q. If we randomly choose coefficients from the set: { -b, -b+1, -b+2. ... -2, -1, 0, 1, 2, ... , b-2, b-1, b} the polynomial will be small with respect to the bound (b).

# Using Discrete Gaussian Sampling - For an odd value for q, the coefficients are randomly chosen by sampling from the set { -(q-1)/2 to (q-1)/2 } according to a discrete gaussian distribution with mean 0 and distribution parameter σ. The references describe in full detail how this can be accomplished. It is more complicated than uniform sampling but it allows for a proof of security of the algorithm. An overview of gaussian sampling is found in a presentation by Peikert.<ref>{{Cite web|title = http://www.cc.gatech.edu/~cpeikert/pubs/slides-pargauss.pdf|url = http://www.cc.gatech.edu/~cpeikert/pubs/slides-pargauss.pdf|website = www.cc.gatech.edu|accessdate = 2015-05-29}}</ref>