Ring learning with errors key exchange: Difference between revisions

Revision as of 01:44, 6 June 2015

Latest revision as of 23:09, 30 August 2024

(112 intermediate revisions by 57 users not shown)

Line 1:

{{technical|date=June 2015}}

{{AFC submission|||u=Carvalho1988|ns=118|ts=20150517232922}} <!-- Do not remove this line! -->

In [[cryptography]], a [[key exchange|public key exchange]] algorithm is a [[cryptographic algorithm]] which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The '''[[ring learning with errors]] key exchange''' ('''RLWE-KEX''') is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a [[quantum computer]]. This is important because some [[public key algorithm]]s in use today will be easily broken by a quantum computer if such computers are implemented. [[Ring learning with errors|RLWE]]-KEX is one of a set of [[post-quantum cryptography|post-quantum cryptographic]] algorithms which are based on the difficulty of solving certain mathematical problems involving [[lattice-based cryptography|lattices]]. Unlike older lattice based cryptographic algorithms, the [[ring learning with errors|RLWE]]-KEX is provably reducible to a known hard problem in lattices.

{{AFC comment|1=Like many mathematical articles on here, this seems far too technical for most Wikipedians to understand; I have a Masters degree in Maths, and can just about understand all of it. Also needs a lead section, per [[MOS:LEAD]]- maybe add some of the background content as a lead? [[User:Joseph2302|Joseph2302]] ([[User talk:Joseph2302|talk]]) 15:45, 2 June 2015 (UTC)}}

== Background ==

----

Since the 1980s the security of cryptographic [[key exchange]]s and [[digital signature]]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 1940s 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. There is optimism in the computer industry that larger scale quantum computers will be available around 2030. If a [[quantum computer]] of sufficient size were built, all of the public key algorithms based on these three classically hard problems would be insecure. This public key cryptography is used today to secure Internet websites, protect computer login information, and prevent our computers from accepting malicious software.

Cryptography that is not susceptible to attack by a quantum computer is referred to as [[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 (computer scientist)|Oded Regev]] in 2005.<ref name=":4">{{Cite book|publisher = ACM|date = 2005|___location = New York, NY, USA|isbn = 978-1-58113-960-0|pages = 84–93|series = STOC '05|doi = 10.1145/1060590.1060603|first = Oded|last = Regev| title=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | chapter=On lattices, learning with errors, random linear codes, and cryptography |citeseerx = 10.1.1.110.4776|s2cid = 53223958}}</ref> A specialized form of Learning with errors operates within the [[polynomial ring|ring of polynomials]] over a [[finite field]]. This specialized form is called [[ring learning with errors]] or [[ideal lattice cryptography|RLWE]].

{{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 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.

There are a variety of cryptographic algorithms which work using the RLWE paradigm. There are [[Public-key cryptography|public-key encryption]] algorithms, [[homomorphic encryption]] algorithms, and [[Ring learning with errors signature|RLWE digital signature]] algorithms in addition to the public key, key exchange algorithm presented in this article

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.

A [[key exchange algorithm]] is a type of public key algorithm which establishes a shared secret key between two communicants on a communications link. The classic example of a key exchange is the [[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 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.

The RLWE Key Exchange is designed to be a "[[Quantum Safe Cryptography|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 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.

=== 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.

== Introduction ==

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

Starting with a [[Prime number|prime]] integer q, the [[Ring learning with errors|Ring-LWE]] key exchange works in the [[ring of polynomials]] modulo a polynomial <math>\Phi(x)</math> with coefficients in the field of integers mod q (i.e. the ring <math>R_q := Z_q[x] / \Phi(x)</math>). Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod <math>\Phi(x)</math>.

The idea of using LWE and Ring LWE for key exchange was first proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper<ref name=":0">{{Cite book|url=https://eprint.iacr.org/2012/688.pdf|title=A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem|last1=Ding|first1=Jintai|last2=Xie|first2=Xiang|last3=Lin|first3=Xiaodong|year=2012}}</ref> appeared in 2012 after a provisional patent application was filed in 2012. The security of the protocol is proven based on the hardness of solving the LWE problem.

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

In 2014, Peikert presented a key-transport scheme<ref>{{Cite journal|last=Peikert|first=Chris|date=2014-01-01|title=Lattice Cryptography for the Internet|journal=Cryptology ePrint Archive |url=https://eprint.iacr.org/2014/070}}</ref> following the same basic idea of Ding's, where the new idea of sending an additional 1-bit signal for rounding in Ding's construction is also used.

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 "New Hope" implementation<ref>{{Cite journal|last1=Alkim|first1=Erdem|last2=Ducas|first2=Léo|last3=Pöppelmann|first3=Thomas|last4=Schwabe|first4=Peter|date=2015-01-01|title=Post-quantum key exchange - a new hope|journal=Cryptology ePrint Archive |url=https://eprint.iacr.org/2015/1092}}</ref> selected for Google's post-quantum experiment,<ref>{{Cite news|url=https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html|title=Experimenting with Post-Quantum Cryptography|newspaper=Google Online Security Blog|access-date=2017-02-08|language=en-US}}</ref> uses Peikert's scheme with variation in the error distribution.

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.

For somewhat greater than 128 [[bits of security]], Singh presents a set of parameters which have 6956-bit public keys for the Peikert's scheme.<ref name=":1">{{Cite journal|last=Singh|first=Vikram|date=2015|title=A Practical Key Exchange for the Internet using Lattice Cryptography|journal=Cryptology ePrint Archive |url=http://eprint.iacr.org/2015/138}}</ref> The corresponding private key would be roughly 14,000 bits. An RLWE version of the classic MQV variant of a Diffie–Hellman key exchange was later published by Zhang et al. in 2014. The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice. This article will closely follow the RLWE work of Ding in "A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem".<ref name=":0">{{Cite book|url=https://eprint.iacr.org/2012/688.pdf|title=A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem|last1=Ding|first1=Jintai|last2=Xie|first2=Xiang|last3=Lin|first3=Xiaodong|year=2012}}</ref> For this presentation a typical polynomial is expressed as:

=== 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:

: <math> a(x) = a₀a_0 + a₁a_1 x + a₂a_2 x^{^2} + ...\cdots + a_{a_{n-3}} x^{^{n-3}} + a_{a_{n-2}} x^{^{n-2}} + a_{a_{n-1}} x<sup>^{n-1} </supmath>

The coefficients of this polynomial, the a<submath>ia_i</submath>'s, of this polynomial are integers &nbsp;mod &nbsp;''q''. The polynomial g<math>\Phi(x)</math> will be gthe [[cyclotomic polynomial]]. When ''n'' is a power of 2 then <math>\Phi(x) = x<sup>^n +1.</supmath><ref +name=":1" where/><ref>{{Cite nweb|title is= aCryptology powerePrint ofArchive: 2Report (nominally2015/1120|url 256,= 512,https://eprint.iacr.org/2015/1120|website or= 1024)eprint.iacr.org|access-date = 2015-12-23}}</ref>

The RingRLWE-LWE key exchangeKEX 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''' vicerather Zthan <math>Zq</qZmath> (i.e.from the set {−(''q''&nbsp;−&nbsp;1)/2,..., 0, ... (''q''&nbsp;−&nbsp;1)/2} ). The algorithm's security will dependdepends 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−b&nbsp;+&nbsp;1, -b−b&nbsp;+&nbsp;2. ... -2−2, -1−1, 0, 1, 2, ... , ''b-''&nbsp;−&nbsp;2, ''b-''&nbsp;−&nbsp;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-''&nbsp;−&nbsp;5, ''q-''&nbsp;−&nbsp;4, ''q-''&nbsp;−&nbsp;3, ''q-''&nbsp;−&nbsp;2, ''q-''&nbsp;−&nbsp;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-&nbsp;−&nbsp;1)/2 to (''q-''&nbsp;−&nbsp;1)/2 } according to a discrete gaussianGaussian distribution with mean 0 and distribution parameter &nbsp;''σ''. 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 gaussianGaussian sampling is found in a presentation by Peikert.<ref>{{Cite web|title = http://www.cc.gatech.edu/~cpeikert/pubs/slides-pargauss.pdfAn Efficient and Parallel Gaussian Sampler for Lattices|url = httphttps://wwwweb.cceecs.gatechumich.edu/~cpeikert/pubs/slides-pargauss.pdf|website = www.cc.gatech.edu|accessdateaccess-date = 2015-05-29}}</ref>

For the rest of this article, the random small polynomials will be sampled according doto 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 The1 maximummod degree2n. ofOther thecases polynomialsfor q and (n) willare bethoroughly adiscussed powerin of"A 2.Toolkit for ThisRing-LWE followsCryptography" and in Singh's "Even More Practical Key Exchange for the workInternet ofusing SinghLattice Cryptography."<ref name=":12">{{Cite journal|last1=Lyubashevsky|first1=Vadim|last2=Peikert|first2=Chris|last3=Regev|first3=Oded|date=2013|title=A Toolkit for Ring-LWE Cryptography|journal=Cryptology ePrint Archive |url=http://eprint.iacr.org/2013/293}}</ref><ref>{{Cite web|title The= otherCryptology casesePrint forArchive: qReport and2015/1120|url n= arehttp://eprint.iacr.org/2015/1120|website thoroughly= discussedeprint.iacr.org|access-date in= the2016-01-17}}</ref> referencedand another paper by PeikertSingh. A fixed public polynomial, a(x), shared by all users of the network. It is deterministically generated from a cryptographically secure source.

Given ''a''(''x'') as stated, we can randomly choose small polynomials ''s''(''x'') and ''e''(''x'') to be the "private key" in a public key exchange. The corresponding public key will be the polynomial ''p''(''x'') = ''a''(''x'')''s''(''x'') + 2''e''(''x'').

=== 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 further understanding the reader should look at the referenced works by Peikert and Singh.<ref name=":0" /><ref name=":1" />

== 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 respondent designated as (R). Both I and R know ''q'', ''n'', ''a''(''x''), and have the ability to generate small polynomials according to the distribution <math>\chi_\alpha</math> with parameter <math>\alpha</math>. The distribution <math>\chi_\alpha</math> is usually the discrete Gaussian distribution on the ring <math> R_q = Z_q[x]/\Phi(x)</math>. 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 a thorough understanding of why the key exchange results in the initiator and responder having the same key, the reader should look at the referenced work by Ding et al.<ref name=":0" />

The key exchange begins with the initiator (I) doing the following:

'''Initiator's First StepsInitiation:'''

# Generate two small polynomials s<submath>Is_I</submath>(x) and e<submath>Ie_I</submath>(x) with small coefficients by sampling from the distribution D<math>\chi_\alpha</math>.

# Compute t<submath>I</sub>(x)p_I = a(x)·s_I(x)as_I + e<sub>I2e_I.</submath>(x).

# The initiator sends the polynomial t<submath>Ip_I</submath>(x) to the Responder.

'''Responder's StepsResponse:'''

# Generate two small polynomials s<submath>Rs_R</submath>(x) and e<submath>Re_R</submath>(x) with small coefficients by sampling from the distribution D<math>\chi_\alpha</math>.

# Compute <math>p_R = as_R + 2e_R</math>.

# 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 no greater than the square of the coefficients of the small be small infinity norm bound.''

# Generate a small <math>e'_R</math> from <math>\chi_\alpha</math>. Compute <math>k_R = p_Is_R+ 2e'_R</math> . Then <math>k_R = as_Is_R + 2e_Is_R + 2e'_R</math>''.''

# 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:

# Use the signal function <math>\operatorname{Sig}</math> to find <math>w = \operatorname{Sig}(k_R) </math>. This is computed by applying <math>Sig</math> function on each coefficient of <math>k_R</math>

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

# Respondent side's key stream <math>sk_R = \operatorname{Mod}_2(k_R,w)</math> is calculated, based on the reconciliation information <math>w</math> and the polynomial <math>k_R</math>.

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

# The Respondent sends <math>p_R</math> and <math>w</math> to the Initiator.

# Two n-long bit streams, uj, and cj, are formed from the coefficients of v(x), (v_n-1, ... , v₀ ), via "Modular Rounding" and "Cross Rounding" respectively. For j = 0 to n-1:

'''Finish:'''

## Find m_j and r_j such that 2v_j = m_jq + r_j

# Receive <math>p_R</math> and <math>w</math> from the Responder.

## Find s_j and y_j such that 4v_j = s_jq + y_j

# Sample <math>e'_I</math> from <math>\chi_\alpha</math> and Compute <math>k_I = p_Rs_I + 2e'_I = as_Is_R + 2e_Rs_I + 2e'_I</math>.

## If r_j > (q-1)/2 (in Z) then set u_j = m_j + 1 (mod 2) otherwise u_j = m_j (mod 2)

# Initiator side's key stream is produced as <math>sk_I = \operatorname{Mod}_2(k_I,w)</math> from the reconciliation information <math>w</math> and polynomial <math>k_I</math>.

## If y_j > (q-1)/2 (in Z) then set c_j = s_j + 1 (mod 2) otherwise c_j = s_j (mod 2)

# Form the key (k) as the concatenation of u_n-1, ..., u₀.

In the above key exchange, <math>\operatorname{Sig}</math> is the signal function defined as below:

# Form an n-long "reconciliation" bit string (c) as the concatenation of c_n-1, ..., c₀.

# Compute t_R(x) = a(x)·s_R(x) + e_R(x).

Define subset <math> \mathbf{E}:=\{-\lfloor \frac{q}{4} \rfloor,\ldots,\lfloor \frac{q}{4}\rceil\}</math> of <math>Zq = \{-\frac{q-1}{2},\ldots,\frac{q-1}{2}\}</math>. Here, <math>\lfloor.\rfloor</math> and <math>\lfloor.\rceil</math>denotes the floor and the rounding to the nearest integer respectively.

# The Responder sends t_R(x) and c to the Initiator.

'''Initiators Final Steps:'''

Function <math>\operatorname{Sig}</math> is the characteristic function of the complement of '''E'''.

# Receive t_R(x) and c from the Responder

# Compute '''w(x) = t_R(x)·s_I(x) + e_I(x)''' = a(x)s_I(x)s_R(x) + e_R(x)s_I(x) + e_I(x) ''Note that while this this does not equal v(x) (above) the first term in the result a(x)s_I(x)s_R(x) equals the first term in v(x) and the other terms are all small. The following reconciliation steps will correct (with high probability) the differences.''

<math>\operatorname{Sig}: Zq \rightarrow \{0,1\}</math>: <math>\operatorname{Sig}(v) = \begin{cases} 0, & \text{if } v \in E \\ 1, & \text{if } v \notin E. \end{cases} </math>

# An n-long bit stream (uj) is formed by looping through the coefficients of w(x) and performing "Key Reconciliation." For j = 0 to n-1:

## If c_j = 0 and -q/8 ≤ w_j < 3q/8 then u_j = 0 otherwise u_j = 1

<math>\operatorname{Mod}_2</math> is the mod 2 operation to eliminate the error terms defined as follows: <math>\operatorname{Mod}_2 (v,w) = \biggl(v + w.\frac{q-1}{2}\Biggr)\bmod q\bmod 2</math>

## If c_j = 1 and q/8 ≤ w_j < 5q/8 then u_j = 0 otherwise u_j = 1

# Form the key (k) as the concatenation of u_n-1, ..., u₀

Note that the values of <math>k_I</math> and <math>k_R</math> are only approximately equal. In order to extract a shared key using this approximate equal values, a reconciliation function, also known as a signal function is used. This function indicates the region in which each coefficient of a polynomial <math>v</math> in <math>R_q</math> lies and helps to make sure that the error terms in <math>k_R</math> and <math>k_I</math> do not result in different mod q operations.

If the key exchange worked properly, the initiator's string: u_n-1, ..., u₀ and the responder's string: u_n-1, ..., u₀ will be the same.

The methods of reconciliation and key string generation depends on the specific RLWE-KEX scheme in question. Some method is based on modular arithmetic, while others may be based on high-dimension geometry.<ref name=":1" /><ref name=":3" />

If the key exchange worked properly, the initiator's string and the respondent's string will be the same.

Depending on the specifics of the parameters chosen, there is an extremely small probability that this key exchange will fail to produce the same key. Parameters for the key exchange can be chosen to make the probability of failure in the key exchange very small; much less than the probability of undetectable garbles or device failures.

== Parameter choices ==

The RLWE-KEX exchange presented above worked in the Ring of Polynomials of degree ''n''&nbsp;−&nbsp;1 or less mod a polynomial <math>\Phi(x)</math>. The presentation assumed that n was a power of 2 and that q was a prime which was congruent to 1 (mod 2n). Following the guidance given in Peikert's paper, Singh suggested two sets of parameters for the RLWE-KEX.

For 128 bits of security, ''n'' = 512, ''q'' = 25601, and <math>\Phi(x) = x^{512} + 1</math>

For 256 bits of security, ''n'' = 1024, ''q'' = 40961, and <math>\Phi(x) = x^{1024} + 1</math>

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 <math display=inline>\frac{8}{\sqrt{2\pi}}</math> 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⁻⁷¹ for the 128-bit secure parameters and <u>less than</u> 2⁻⁹¹ for the 256-bit secure parameters.

In their November 2015 paper, Alkim, Ducas, Pöppelmann, and Schwabe recommend the following parameters n = 1024, q =12289, and <math>\Phi(x)</math> = x¹⁰²⁴ + 1.<ref name=":3" /> This represents a 70% reduction in public key size over the n = 1024 parameters of Singh, and was submitted to NIST's [[Post-Quantum Cryptography Standardization]] project under the name [[NewHope]].

Also in their November 2015 paper, Alkim, Ducas, Pöppelmann and Schwabe recommend that the choice of the base polynomial for the key exchange ( a(x) above ) be either generated randomly from a secure random number generator for each exchange or created in a verifiable fashion using a "nothing up my sleeve" or NUMS technique.<ref name=":3" /> An example of parameters generated in this way are the prime numbers for the Internet Key Exchange (<nowiki>RFC 2409</nowiki>) which embed the digits of the mathematical constant pi in the digital representation of the prime number.<ref>{{Cite journal|url=https://tools.ietf.org/html/rfc2409|title=The Internet Key Exchange (IKE)|last1=D.|first1=Carrel|last2=D.|first2=Harkins|website=tools.ietf.org|date=November 1998 |language=en|access-date=2017-03-16}}</ref> Their first method prevents amortization of attack costs across many key exchanges at the risk of leaving open the possibility of a hidden attack like that described by Dan Bernstein against the NIST elliptic curves.<ref>{{Cite web|url=https://crypto.stackexchange.com/q/35488 |title=Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?|website=crypto.stackexchange.com|access-date=2017-03-16}}</ref> The NUMS approach is open to amortization but generally avoids the Bernstein attack if only common mathematical constants such as pi and e are used.

== Key exchange security ==

Depending on the specifics of the parameters chosen n, q, σ, or b, there is an extremely small probability that this key exchange will fail to produce the same key. Implementors of the scheme might want to introduce a key validation step before ciphertext is produced.

The security of this key exchange is based on the underlying hardness of [[ring learning with errors]] problem that has been proven to be as hard as the worst case solution to the [[shortest vector problem]] (SVP) in an [[ideal lattice cryptography|ideal lattice]].<ref name=":4" /><ref name=":0" /> The best method to gauge the practical security of a given set of lattice parameters is the BKZ 2.0 lattice reduction algorithm.<ref>{{Cite book|publisher = Springer Berlin Heidelberg|date = 2011|isbn = 978-3-642-25384-3|pages = 1–20|series = Lecture Notes in Computer Science|first1 = Yuanmi|last1 = Chen|first2 = Phong Q.|last2 = Nguyen| title=Advances in Cryptology – ASIACRYPT 2011 | chapter=BKZ 2.0: Better Lattice Security Estimates | volume=7073 |editor-first = Dong Hoon|editor-last = Lee|editor-first2 = Xiaoyun|editor-last2 = Wang|doi = 10.1007/978-3-642-25385-0_1}}</ref> According to the BKZ 2.0 algorithm the key exchange parameters listed above will provide greater than 128 or 256 bits of security, respectively.

==Implementations==

=== Parameter Choices ===

In 2014 Douglas Stebila made [http://www.douglas.stebila.ca/research/papers/bcns15 a patch] for OpenSSL 1.0.1f. based on his work and others published in "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem."<ref>{{Cite journal|title = Post-quantum key exchange for the TLS protocol from the ring learning with errors problem|url = http://eprint.iacr.org/2014/599|date = 2014-01-01|first1 = Joppe W.|last1 = Bos|first2 = Craig|last2 = Costello|first3 = Michael|last3 = Naehrig|first4 = Douglas|last4 = Stebila| journal=Cryptology ePrint Archive }}</ref> Software implementing the work of Singh is found on GitHub at [https://github.com/vscrypto/ringlwe https://github.com/vscrypto/ringlwe.]<ref name=":1" />

The Ring-LWE Key exchange presented above worked in the Ring of Polynomials of degree n-1 or less mod a polynomial F(x). The presentation assumed that n was a power of 2 and that q was a prime which was congruent to 1 (mod 4). Following the guidance given in Peikert's paper, Singh suggested two sets of paramters for the Ring-LWE Key Exchange.

== Other approaches ==

For 128 bits of security, n = 512, q = 25601, and F(x) = x⁵¹² + 1

A variant of the approach described above is an authenticated version in the work of Zhang, Zhang, Ding, Snook and Dagdelen in their paper, "Post Quantum Authenticated Key Exchange from Ideal Lattices."<ref>{{Cite journal|title = Workshop on Cybersecurity in a Post-Quantum World|url = https://www.nist.gov/itl/csd/ct/post-quantum-crypto-workshop-2015.cfm|journal = NIST|access-date = 2015-06-06|date = 2015-04-02}}</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 = Noisy Diffie–Hellman protocols|url = https://pqc2010.cased.de/rr/03.pdf|website = pqc2010.cased.de|access-date = 2015-06-06|archive-url=https://web.archive.org/web/20150614110435/https://pqc2010.cased.de/rr/03.pdf |archive-date=2015-06-14 |url-status=dead}}</ref>

In November 2015, Alkim, Ducas, Pöppelmann, and Schwabe built on the prior work of Peikert and used what they believe is a more conservative costing of lattice attacks to recommend parameters.<ref name=":3">{{Cite web|title = Cryptology ePrint Archive: Report 2015/1092|url = https://eprint.iacr.org/2015/1092|website = eprint.iacr.org|access-date = 2015-11-11}}</ref> Software based on the work of Alkim, Ducas, Pöppelmann, and Schwabe is found on GitHub at https://github.com/tpoeppelmann/newhope<ref name=":3" />

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

== See also ==

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.

* [[Post-quantum cryptography]]

* [[Lattice-based cryptography]]

* [[Ideal lattice cryptography]]

* [[Ring learning with errors signature]]

* [[Ring learning with errors]]

== References ==

=== Key Exchange Security ===

{{reflist}}

The security of this Ring-LWE key exchange is based on the difficulty of problems involving i[[Lattices|nteger lattices]] (see link for more information). In particular the security of this key exchange is based on the difficulty of find the shortest vector in a lattice. This is known as the [[Shortest vector problem|Shortest Vector Problem]] (SVP). The best algorithm for solving is problem is the BKZ 2.0 lattice reduction algorithm. <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> According to the BKZ 2.0 algorithm the key exchange parameters listed above will provide greater than 128 or 256 bits of security, respectively. It is also worth noting that in his referenced paper Peikert demonstrates that there is a provable security equivalence between breaking this key exchange and in an integer lattice.<ref name=":0" />

==External links==

=== 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>{{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>

{{ Cryptography navbox | public-key }}

=== References ===

<references />

[[:Category:Cryptographic algorithms]]

[[Category:Post-quantum cryptography]]

[[Category:Lattice-based cryptography]]