Ring learning with errors key exchange: Difference between revisions

Revision as of 06:33, 29 July 2017

Revision as of 21:13, 30 August 2017

Line 15:

== Introduction ==

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 Φ<nowiki><math>\Phi(x)</math></nowiki> with coefficients in the field of integers mod q (i.e. the ring R<sub>q</submath>R_q := <math>Zq</math>Z_q[x] /Φ \Phi(x) </math>). Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod Φ<nowiki><math>\Phi(x)</math></nowiki><math>\Phi(x)</math>.

In 2014, Peikert<ref>{{Cite journal|last=Peikert|first=Chris|date=2014-01-01|title=Lattice Cryptography for the Internet|url=http://eprint.iacr.org/2014/070|journal=|volume=|issue=|doi=|pmid=|access-date=|via=}}</ref> presented a key transport scheme based on Ring-LWE. 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|url=http://eprint.iacr.org/2015/138}}</ref> The corresponding private key would be roughly 14000 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|last=Ding|first=Jintai|last2=Xie|first2=Xiang|last3=Lin|first3=Xiaodong|publisher=|year=2012|isbn=|___location=|pages=|via=}}</ref> For this presentation a typical polynomial is expressed as:

Line 21:

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 Φ<nowiki><math>\Phi(x)</math></nowiki> will be the [[cyclotomic polynomial]]. When n is a power of 2 then Φ<nowiki><math>\Phi(x)</math></nowiki> = xⁿ +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>

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

Line 31:

== 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_q = <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 key exchange begins with the initiator (I) doing the following:

Line 71:

== Parameter choices ==

The RWLE-KEX exchange presented above worked in the Ring of Polynomials of degree n-1 or less mod a polynomial Φ<nowiki><math>\Phi(x)</math></nowiki>. 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 Φ<nowiki><math>\Phi(x)</math></nowiki> = x⁵¹² + 1

For 256 bits of security, n = 1024, q = 40961, and Φ<nowiki><math>\Phi(x)</math></nowiki> = x¹⁰²⁴ + 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),<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, Popplemann, and Schwabe recommend the following parameters n = 1024, q =12289, and Φ<nowiki><math>\Phi(x)</math></nowiki> = x¹⁰²⁴ + 1.<ref name=":3" /> This represents a 70% reduction in public key size over the n = 1024 parameters of Singh. A listing of a number of different parameter choices for key exchanges using the Ring Learning with Errors problem are given at this link ([http://www.ringlwe.info/parameters-for-rlwe.html click here]).<ref>{{Cite web

| url = http://www.ringlwe.info/parameters-for-rlwe.html

| title = Parameters for RLWE