Content deleted Content added
→The key exchange: fixed typo Z_a not Zq Tags: Mobile edit Mobile web edit |
|||
| (42 intermediate revisions by 31 users not shown) | |||
Line 1:
{{technical|date=June 2015}}
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 '''[[
== 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 [[
There are a variety of cryptographic algorithms which work using the RLWE paradigm. There are [[Public-key cryptography|public
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 RLWE Key Exchange is designed to be a "[[Quantum Safe Cryptography|quantum safe]]" replacement for the widely used [[
== Introduction ==
Starting with a [[Prime number|prime]] integer q, the [[Ring
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.
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 coefficients of this polynomial, the a<sub>i</sub>'s, are integers mod q. The polynomial <math>\Phi(x)</math> will be the [[cyclotomic polynomial]]. When n is a power of 2 then <math>\Phi(x)</math> = x<sup>n</sup> +1.<ref name=":1" /><ref>{{Cite web|title = Cryptology ePrint Archive: Report 2015/1120|url = https://eprint.iacr.org/2015/1120|website = eprint.iacr.org|accessdate = 2015-12-23}}</ref>▼
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:
The RLWE-KEX 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 rather than <math>Zq</math>(i.e.from the set {-(q-1)/2,..., 0, ... (q-1)/2} ). The algorithm's security depends 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<sub>n-1</sub>, ..., s<sub>0</sub>) 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 = An Efficient and Parallel Gaussian Sampler for Lattices|url = https://web.eecs.umich.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 to a distribution which is simply specified as '''D'''. Further q will be an odd prime such that q is congruent to 1 mod 4 and 1 mod 2n. Other cases for q and n are thoroughly discussed in "A Toolkit for Ring-LWE Cryptography" and in Singh's "Even More Practical Key Exchange for the Internet using Lattice Cryptography."<ref name=":2">{{Cite journal|last=Lyubashevsky|first=Vadim|last2=Peikert|first2=Chris|last3=Regev|first3=Oded|date=2013|title=A Toolkit for Ring-LWE Cryptography|url=http://eprint.iacr.org/2013/293}}</ref><ref>{{Cite web|title = Cryptology ePrint Archive: Report 2015/1120|url = http://eprint.iacr.org/2015/1120|website = eprint.iacr.org|access-date = 2016-01-17}}</ref> and another paper by Singh. A fixed public polynomial, a(x), shared by all users of the network. It is deterministically generated from a cryptographically secure source.▼
: <math> a(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-3} x^{n-3} + a_{n-2} x^{n-2} + a_{n-1} x^{n-1} </math>
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) + 2e(x).▼
▲The coefficients <math>a_i</math> of this polynomial
== 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 R<sub>q</sub> = <math>Zq</math>[x]/<nowiki><math>\Phi(x)</math></nowiki>. 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 RLWE-KEX 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''' rather than <math>Zq</math> (i.e.from the set {
▲# Using [[Uniform distribution (discrete)|Uniform Sampling]]
▲# Using [[Gaussian distribution|Discrete Gaussian]] Sampling
▲For the rest of this article, the random small polynomials will be sampled according to a distribution which is simply specified as '''D'''. Further q will be an odd prime such that q is congruent to 1 mod 4 and 1 mod 2n. Other cases for q and n are thoroughly discussed in "A Toolkit for Ring-LWE Cryptography" and in Singh's "Even More Practical Key Exchange for the Internet using Lattice Cryptography."<ref name=":2">{{Cite journal|
▲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'') +
▲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
The key exchange begins with the initiator (I) doing the following:
Line 37 ⟶ 43:
'''Initiation:'''
# Generate two polynomials <math>s_I</math> and <math>e_I</math> with small coefficients by sampling from the distribution <math>\chi_\alpha</math>.
# Compute <math>p_I = as_I + 2e_I.</math>
# The initiator sends the polynomial <math>p_I</math> to the Responder.
'''Response:'''
Line 43 ⟶ 49:
# Compute <math>p_R = as_R + 2e_R</math>.
# 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>''.''
# 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>
# Respondent side's key stream <math>sk_R =
# The Respondent sends <math>p_R</math> and <math>w</math> to the Initiator.
'''Finish:'''
# Receive <math>p_R</math> and <math>w</math> from the Responder.
# 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>.
# Initiator side's key stream is produced as <math>sk_I =
In the above key exchange, <math>\operatorname{Sig}</math> is the signal function defined as below:▼
▲# Initiator side's key stream is produced as <math>sk_I = Mod_2(k_I,w)</math> from the reconciliation information <math>w</math> and polynomial <math>k_I</math>.
Define subset
▲In the above key exchange, <math>Sig</math> is the signal function defined as below:
Function <math>\operatorname{Sig}</math> is the characteristic function of the complement of '''E'''.▼
▲Define subset '''E''':=<math>\{-\lfloor \frac{q}{4} \rfloor,...,\lfloor \frac{q}{4}\rceil\}</math> of <math>Zq</math> = <math>\{-\frac{q-1}{2},...,\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.
<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>▼
▲Function <math>Sig</math> is the characteristic function of the complement of '''E'''.
<math>
▲<math>Sig: Zq \rightarrow \{0,1\}</math>: <math>Sig(v) = \begin{cases} 0, & \text{if } v \in E \\ 1, & \text{if }v \notin E \end{cases} </math>
▲<math>Mod_2</math> is the mod 2 operation to eliminate the error terms defined as follows: <math>Mod_2 (v,w) = \biggl(v + w.\frac{q-1}{2}\Biggr)\text{ mod }q\text{ mod 2}</math>
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.
Line 71 ⟶ 76:
== Parameter choices ==
The
For 128 bits of security,
For 256 bits of security, ''n'' = 1024, ''q'' = 40961, and
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
In their November 2015 paper, Alkim, Ducas,
Also in their November 2015 paper, Alkim, Ducas,
== Key
The security of this key exchange is based on the underlying hardness of [[
==Implementations==
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
== Other approaches ==
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
In November 2015, Alkim, Ducas,
== See also ==
Line 103:
* [[Lattice-based cryptography]]
* [[Ideal lattice cryptography]]
* [[Ring learning with errors signature
* [[Ring == References ==
{{reflist}}
==External links==
{{ Cryptography navbox | public-key }}
[[Category:Cryptographic algorithms]]
[[Category:Post-quantum cryptography]]
[[Category:Lattice-based cryptography]]
| |||