Ring learning with errors key exchange: Difference between revisions

Revision as of 14:08, 6 June 2015

Revision as of 01:44, 10 June 2015

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 of information and its intended recipient can createproduce a shared secret, keythat is, a secret that only they both shareknow.

This article isfocuses abouton a specialparticular set of cryptographic [[computer algorithms]] called public [[key exchange]] algorithms. In these algorithms a sender ("Initiator" of the key exchange) and athe intended recipient ("Responder in the key exchange) each generate random information and combine this information with fixed and known information to form a public key. The sender and intended 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 forform 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.

=== 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 (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 ResistantSafe]], or [[Post-quantum cryptography|Quantum Safe]], or [[Post-quantumQuantum 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 signature]] algorithms in addition to the public key, key exchange algorithm presented in this article

Line 23:

=== Introduction ===

Starting with a [[Prime number|prime]] integer q, 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 (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. The polynomial gφ(x) will be gφ(x) = xⁿ +1 where n is a power of 2 (nominallyn = 256, 512, or 1024 are usually referenced in the academic literature).

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 distribution (discrete)|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). Singh suggest using b = 5.<ref name=":1" /> Thus coefficients would be chosen from the set { q-5, q-4, q-3, q-2, q-1, 0 , 1, 2, 3, 4, 5 }.

# Using [[Gaussian distribution|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>

For the rest of this article, the random small polynomials will be sampled according do a distribution which is simply be specified as '''D'''. Further q will be an odd prime such that q is congruent to 1 mod 4 and 1 mod 2n. The maximum degree of the polynomials (n) will be a power of 2. This follows the work of Singh.<ref name=":1" /> The otherOther cases for q and n are thoroughly discussed in the"A referencedToolkit paperfor byRing-LWE PeikertCryptography."<ref name=":2" /> A fixed public polynomial, a(x), shared by all users of the network. It is deterministically generated from a cryptographically secure source.

=== The Key Exchange ===

Line 45:

'''Responder's Steps:'''

# Generate two small polynomials s_R(x) and e_R(x) by sampling from the distribution D.

# Compute '''v(x) =''' '''t_I(x)·s_R(x) + e_R(x)''' ''Note that v(x) = a(x)s_I(x)s_R(x) + e_I(x)s_R(x) + e_R(x) and that e_R(x) + e_I(x)s_R(x) will be small because e_R(x) was chosen to be small and the coefficients of e_I(x)s_R(x) will be nobounded greaterin thantheir thegrowth squareand ofstill the coefficients of therelatively small be small infinity norm bound.''

# The distribution of the coefficients of v(x) are smoothed by looping through the coefficients and randomly adjusting certain values. For j = 0 to n-1:

## If v_j = 0, draw a random bit (b). If b = 0 then v_j = 0 otherwise v_j = q-1

Line 82:

=== Other Approaches ===

A variant of the approach described above but with very different reconciliation function and parameter choices is the work of Zhang, Zhang, Ding, Snook and Dagdelen in their paper, "Post Quantum Authenticated Key Exchange from Ideal Lattices."<ref>{{Cite web|title = Workshop on Cybersecurity in a Post-Quantum World|url = http://www.nist.gov/itl/csd/ct/post-quantum-crypto-workshop-2015.cfm|website = www.nist.gov|accessdate = 2015-06-06}}</ref> The concept of creating what has been called a Diffie-Hellman-like Key Exchange using lattices with a reconciliation function appears to have first been presented by French researchers Aguilar, Gaborit, Lacharme, Schrek, and Zemor at PQCrypto 2010 in their talk, "Noisy Diffie-Hellman Protocols."<ref>{{Cite web|title = https://pqc2010.cased.de/rr/03.pdf|url = https://pqc2010.cased.de/rr/03.pdf|website = pqc2010.cased.de|accessdate = 2015-06-06}}</ref> This work was then extended and put on a much more rigorous foundation by Peikert in his writings.<ref name=":0" /><ref name=":2">{{Cite journal|title = A Toolkit for Ring-LWE Cryptography|url = http://eprint.iacr.org/2013/293|date = 2013|first = Vadim|last = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev}}</ref>

=== References ===