Jump to content

Ring learning with errors key exchange

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Carvalho1988 (talk | contribs) at 14:08, 6 June 2015 (Cleaned up grammar). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

  • Comment: 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? Joseph2302 (talk) 15:45, 2 June 2015 (UTC)

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 and intended recipient can create a secret key that they both share.

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. This article discusses a different key exchange that has many of the same properties as the 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 for of public key exchange is used. A 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 exchanges and digital signatures 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 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 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 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[1]. 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.

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 signature algorithms in addition to the public key, key exchange algorithm presented in this article

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. The exchange consists of one transmission from one end of the line and one transmission from the other end of the link. Diffie-Hellman and Elliptic Curve Diffie-Hellman are the two most popular key exchange algorithms.

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.

Introduction

Starting with a 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 Fq[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 [2][3]. For this presentation a typical polynomial is expressed as:

a(x) = a0 + a1x + a2x2 + ... + an-3xn-3 + an-2xn-2 + an-1xn-1

The coefficients of this polynomial, the ai's, are integers mod q. The polynomial g(x) will be g(x) = xn +1 where n is a power of 2 (nominally 256, 512, or 1024).

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 (sn-1, ..., s0) which are guaranteed or very likely to be small. There are two common ways to do this:

  1. 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). Singh suggest using b = 5.[3] Thus coefficients would be chosen from the set { q-5, q-4, q-3, q-2, q-1, 0 , 1, 2, 3, 4, 5 }.
  2. 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. An overview of gaussian sampling is found in a presentation by Peikert.[4]

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.[3] The other cases for q and n are thoroughly discussed in the referenced paper by Peikert. 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 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 works by Peikert and Singh.[2][3]

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

Initiator's First Steps:

  1. Generate two small polynomials sI(x) and eI(x) by sampling from the distribution D.
  2. Compute tI(x) = a(x)·sI(x) + eI(x).
  3. The initiator sends the polynomial tI(x) to the Responder.

Responder's Steps:

  1. Generate two small polynomials sR(x) and eR(x) by sampling from the distribution D.
  2. Compute v(x) = tI(x)·sR(x) + eR(x) Note that v(x) = a(x)sI(x)sR(x) + eI(x)sR(x) + eR(x) and that eR(x) + eI(x)sR(x) will be small because eR(x) was chosen to be small and the coefficients of eI(x)sR(x) will be no greater than the square of the coefficients of the small be small infinity norm bound.
  3. 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:
    1. If vj = 0, draw a random bit (b). If b = 0 then vj = 0 otherwise vj = q-1
    2. If vj = (q-1)/4, draw a random bit (b). If b = 0 then vj = (q-1)/4 otherwise vj = (q+3)/4
  4. Two n-long bit streams, uj, and cj, are formed from the coefficients of v(x), (vn-1, ... , v0 ), via "Modular Rounding" and "Cross Rounding" respectively. For j = 0 to n-1:
    1. Find mj and rj such that 2vj = mjq + rj
    2. Find sj and yj such that 4vj = sjq + yj
    3. If rj > (q-1)/2 (in Z) then set uj = mj + 1 (mod 2) otherwise uj = mj (mod 2)
    4. If yj > (q-1)/2 (in Z) then set cj = sj + 1 (mod 2) otherwise cj = sj (mod 2)
  5. Form the key (k) as the concatenation of un-1, ..., u0.
  6. Form an n-long "reconciliation" bit string (c) as the concatenation of cn-1, ..., c0.
  7. Compute tR(x) = a(x)·sR(x) + eR(x).
  8. The Responder sends tR(x) and c to the Initiator.

Initiators Final Steps:

  1. Receive tR(x) and c from the Responder
  2. Compute w(x) = tR(x)·sI(x) + eI(x) = a(x)sI(x)sR(x) + eR(x)sI(x) + eI(x) Note that while this this does not equal v(x) (above) the first term in the result a(x)sI(x)sR(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.
  3. 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:
    1. If cj = 0 and -q/8 ≤ wj < 3q/8 then uj = 0 otherwise uj = 1
    2. If cj = 1 and q/8 ≤ wj < 5q/8 then uj = 0 otherwise uj = 1
  4. Form the key (k) as the concatenation of un-1, ..., u0

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

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) = x512 + 1

For 256 bits of security, n = 1024, q = 40961, and F(x) = x1024 + 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. If we assume that the gaussian parameter σ is 8/sqrt(2π) and the uniform sampling bound (b) = 5 (see Singh)[3], then the probability of key agreement failure is less than 2-71 for the 128-bit secure parameters and less than 2-91 for the 256-bit secure parameters.

Key Exchange Security

The security of this Ring-LWE key exchange is based on the difficulty of problems involving integer 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 (SVP). The best algorithm for solving is problem is the BKZ 2.0 lattice reduction algorithm. [5] 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.[2]

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."[6] 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."[7] This work was then extended and put on a much more rigorous foundation by Peikert in his writings.[2][8]

References

  1. ^ Regev, Oded (2005). "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing. STOC '05. New York, NY, USA: ACM: 84–93. doi:10.1145/1060590.1060603. ISBN 1-58113-960-8.
  2. ^ a b c d Peikert, Chris (2014). Mosca, Michele (ed.). Lattice Cryptography for the Internet. Lecture Notes in Computer Science. Springer International Publishing. pp. 197–219. ISBN 978-3-319-11658-7.
  3. ^ a b c d e Singh, Vikram (2015). "A Practical Key Exchange for the Internet using Lattice Cryptography". {{cite journal}}: Cite journal requires |journal= (help)
  4. ^ "http://www.cc.gatech.edu/~cpeikert/pubs/slides-pargauss.pdf" (PDF). www.cc.gatech.edu. Retrieved 2015-05-29. {{cite web}}: External link in |title= (help)
  5. ^ Chen, Yuanmi; Nguyen, Phong Q. (2011). Lee, Dong Hoon; Wang, Xiaoyun (eds.). BKZ 2.0: Better Lattice Security Estimates. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1–20. ISBN 978-3-642-25384-3.
  6. ^ "Workshop on Cybersecurity in a Post-Quantum World". www.nist.gov. Retrieved 2015-06-06.
  7. ^ "https://pqc2010.cased.de/rr/03.pdf" (PDF). pqc2010.cased.de. Retrieved 2015-06-06. {{cite web}}: External link in |title= (help)
  8. ^ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2013). "A Toolkit for Ring-LWE Cryptography". {{cite journal}}: Cite journal requires |journal= (help)

Category:Cryptographic algorithms

Retrieved from "https://en.wikipedia.org/w/index.php?title=Ring_learning_with_errors_key_exchange&oldid=665760281"