User:Carvalho1988: Difference between revisions
Content deleted Content added
Carvalho1988 (talk | contribs) No edit summary |
Carvalho1988 (talk | contribs) ←Blanked the page |
||
| Line 1: | Line 1: | ||
=== 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 [[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 Quantum Resistant, 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 Ring-LWE. |
|||
=== Introduction === |
|||
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<sub>q</sub>[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 name=":0">{{Cite journal|title = Lattice Cryptography for the Internet|url = http://eprint.iacr.org/2014/070|date = 2014|first = Chris|last = Peikert}}</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<sub>n-1</sub>x<sup>n-1</sup> + p<sub>n-2</sub>x<sup>n-2</sup> + p<sub>n-3</sub>x<sup>n-3</sup> + ... + p<sub>2</sub>x<sup>2</sup> + p<sub>1</sub>x + p<sub>0</sub> |
|||
This cryptographic algorithm 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 considered as integers in (Z vice Z/pZ). The algorithm will generate random polynomials which are small with respect to the infinity norm. We do this by randomly generating the coefficients of the polynomial (p<sub>n-1</sub>, ..., p<sub>0</sub>) 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. |
|||
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. The maximum degree of the polynomials (n) will be a power of 2. This follows the work of Singh.<ref name=":1" /> The other cases for q and n are thoroughly discussed in the referenced paper by Peikert.<ref name=":0" /> 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 === |
|||
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 key exchange begins with the initiator (I) doing the following: |
|||
'''Initiator's First Steps:''' |
|||
# Generate two small polynomials s<sub>I</sub>(x) and e<sub>I</sub>(x) by sampling from the distribution D. |
|||
# Compute t<sub>I</sub>(x) = a(x)·s<sub>I</sub>(x) + e<sub>I</sub>(x). |
|||
# The initiator sends the polynomial t<sub>I</sub>(x) to the Responder. |
|||
'''Responser's Steps:''' |
|||
# Generate two small polynomials s<sub>R</sub>(x) and e<sub>R</sub>(x) by sampling from the distribution D. |
|||
# Compute v(x) = t<sub>I</sub>(x)·s<sub>R</sub>(x) + e<sub>R</sub>(x) Note that this equals: a(x)s<sub>I</sub>(x)s<sub>R</sub>(x) + e<sub>I</sub>(x)s<sub>R</sub>(x) + e<sub>R</sub>(x) and that e<sub>I</sub>(x)s<sub>R</sub>(x) will also be small relative to the infinity norm on q. |
|||
# 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<sub>j</sub> = 0, draw a random bit (b). If b = 0 then v<sub>j</sub> = 0 otherwise v<sub>j</sub> = q-1 |
|||
## If v<sub>j</sub> = (q-1)/4, draw a random bit (b). If b = 0 then v<sub>j</sub> = (q-1)/4 otherwise v<sub>j</sub> = (q+3)/4 |
|||
# Two n-long bit streams, uj, and cj, are formed from the coefficients of v(x), (v<sub>n-1</sub>, ... , v<sub>0</sub> ), via "Modular Rounding" and "Cross Rounding" respectively. For j = 0 to n-1: |
|||
## Find m<sub>j</sub> and r<sub>j</sub> such that 2v<sub>j</sub> = m<sub>j</sub>q + r<sub>j</sub> |
|||
## Find s<sub>j</sub> and y<sub>j</sub> such that 4v<sub>j</sub> = s<sub>j</sub>q + y<sub>j</sub> |
|||
## If r<sub>j</sub> > (q-1)/2 (in Z) then set u<sub>j</sub> = m<sub>j</sub> + 1 (mod 2) otherwise u<sub>j</sub> = m<sub>j</sub> (mod 2) |
|||
## If y<sub>j</sub> > (q-1)/2 (in Z) then set c<sub>j</sub> = s<sub>j</sub> + 1 (mod 2) otherwise c<sub>j</sub> = s<sub>j</sub> (mod 2) |
|||
# Form the key (k) as the concatenation of u<sub>n-1</sub>, ..., u<sub>0</sub>. |
|||
# Form an n-long "reconciliation" bit string (c) as the concatenation of c<sub>n-1</sub>, ..., c<sub>0</sub>. |
|||
# Compute t<sub>R</sub>(x) = a(x)·s<sub>R</sub>(x) + e<sub>R</sub>(x). |
|||
# The Responder sends t<sub>R</sub>(x) and c to the Initiator. |
|||
'''Initiators Final Steps:''' |
|||
# Receive t<sub>R</sub>(x) and c from the Responder |
|||
# Compute w(x) = t<sub>R</sub>(x)·s<sub>I</sub>(x) + e<sub>I</sub>(x) = a(x)s<sub>I</sub>(x)s<sub>R</sub>(x) + e<sub>R</sub>(x)s<sub>I</sub>(x) + e<sub>I</sub>(x) Note that this does not equal v(x) (above) but is "close." |
|||
# 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<sub>j</sub> = 0 and -q/8 ≤ w<sub>j</sub> < 3q/8 then u<sub>j</sub> = 0 otherwise u<sub>j</sub> = 1 |
|||
## If c<sub>j</sub> = 1 and q/8 ≤ w<sub>j</sub> < 5q/8 then u<sub>j</sub> = 0 otherwise u<sub>j</sub> = 1 |
|||
# Form the key (k) as the concatenation of u<sub>n-1</sub>, ..., u<sub>0</sub> |
|||
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. |
|||
=== Parameter Choices === |
|||
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. |
|||
For 128 bits of security, n = 512, q = 25601, and F(x) = x<sup>512</sup> + 1 |
|||
For 256 bits of security, n = 1024, q = 40961, and F(x) = x<sup>1024</sup> + 1 |
|||
These choices of parameters will provide greater than 128 or 256 bits of security, respectively. 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<sup>-71</sup> for the 128-bit secure parameters and 2<sup>-91</sup> for the 256-bit secure parameters. |
|||
=== References === |
|||