Ring learning with errors key exchange: Difference between revisions

Revision as of 16:25, 26 May 2015

Revision as of 16:39, 26 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 based on a small number of [[public key]] algorithms. The security of these algorithms is based on a 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 computer. If a [[quantum computer]] of sufficient size were build, all of the public key algorithms based on these 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 specializedspecialised 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 10:

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.

The Ring-LWE key exchange works in the ring of polynomials of degree n-1 or less modulo a polynomial F(x) (i.e. the ring Z_q[x]/F(x) for an integer q). The coefficients of the polynomials in this ring are the integers mod q. Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod F(x). This article will closely follow the work of Peikert as further explained by Singh <ref>{{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/10/01|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:

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

Line 57:

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. This is generally referred to as the soundness of the 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 2^-91 for the 256-bit secure parameters'''.

Based on the BKZ 2.0 lattice reduction approach, these choices of parameters will provide greater than 128 or 256 bits of security, respectively. <ref>{{Cite book|title = BKZ 2.0: Better Lattice Security Estimates|url = http://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|language = en|first = Yuanmi|last = Chen|first2 = Phong Q.|last2 = Nguyen|editor-first = Dong Hoon|editor-last = Lee|editor-first2 = Xiaoyun|editor-last2 = Wang}}</ref>

=== Key Exchange Security ===

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 2^-91 for the 256-bit secure parameters.

Based on the BKZ 2.0 lattice reduction approachalgorithm, these choices of parameters will provide greater than 128 or 256 bits of security, respectively. <ref>{{Cite book|title = BKZ 2.0: Better Lattice Security Estimates|url = http://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|language = en|first = Yuanmi|last = Chen|first2 = Phong Q.|last2 = Nguyen|editor-first = Dong Hoon|editor-last = Lee|editor-first2 = Xiaoyun|editor-last2 = Wang}}</ref> It is also worth noting that Peikert demonstrates that there is a provable security equivalence between breaking this key exchange and the [[Shortest vector problem|Shortest Vector Problem]] (SVP) in an integer lattice.

=== References ===