Ring learning with errors key exchange: Difference between revisions

Revision as of 17:59, 23 November 2019

Revision as of 18:42, 23 November 2019

Line 79:

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/&radic;(2{{pi}}) 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 <math>\Phi(x)</math> = x¹⁰²⁴ + 1.<ref name=":3" /> This represents a 70% reduction in public key size over the n = 1024 parameters of Singh, and was submitted to NIST's [[Post-Quantum Cryptography Standardization]] project under the name [[NewHope]]. 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

| website = Ring Learning with Errors

| access-date = 2016-02-28

}}</ref>

Also in their November 2015 paper, Alkim, Ducas, Popplemann and Schwabe recommend that the choice of the base polynomial for the key exchange ( a(x) above ) be either generated randomly from a secure random number generator for each exchange or created in a verifiable fashion using a "nothing up my sleeve" or NUMS technique.<ref name=":3" /> An example of parameters generated in this way are the prime numbers for the Internet Key Exchange (<nowiki>RFC 2409</nowiki>) which embed the digits of the mathematical constant pi in the digital representation of the prime number.<ref>{{Cite web|url=https://tools.ietf.org/html/rfc2409|title=The Internet Key Exchange (IKE)|last=D.|first=Carrel|last2=D.|first2=Harkins|website=tools.ietf.org|language=en|access-date=2017-03-16}}</ref> Their first method prevents amortization of attack costs across many key exchanges at the risk of leaving open the possibility of a hidden attack like that described by Dan Bernstein against the NIST elliptic curves.<ref>{{Cite web|url=https://crypto.stackexchange.com/q/35488 |title=Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?|website=crypto.stackexchange.com|access-date=2017-03-16}}</ref> The NUMS approach is open to amortization but generally avoids the Bernstein attack if only common mathematical constants such as pi and e are used.