Ring learning with errors key exchange: Difference between revisions

Revision as of 02:12, 21 February 2019

Revision as of 11:49, 23 February 2019

Line 25:

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''&nbsp;−&nbsp;1)/2,..., 0, ... (''q''&nbsp;−&nbsp;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:

# 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&nbsp;+&nbsp;1, −b&nbsp;+&nbsp;2. ... −2, −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''&nsbpnbsp;−&nbsp;1)/2 } according to a discrete Gaussian 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 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.