Ring learning with errors key exchange: Difference between revisions

Revision as of 13:28, 13 December 2017

Revision as of 15:39, 19 October 2018

Line 88:

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=http://crypto.stackexchange.com/questions/35488/is-the-new-hope-lattice-key-exchange-vulnerable-to-a-lattice-analog-of-the-ber|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.

== Key Exchangeexchange Securitysecurity ==

The security of this key exchange is based on the underlying hardness of [[Ringring Learninglearning with Errors|Ring Learning With Errorserrors]] problem that has been proven to be as hard as the worst case solution to the [[Shortestshortest vector problem|Shortest Vector Problem]] (SVP) in an [[Idealideal lattice cryptography|Idealideal Latticelattice]].<ref name=":4" /><ref name=":0" /> The best method to gauge the practical security of a given set of lattice parameters is the BKZ 2.0 lattice reduction algorithm.<ref>{{Cite book|title = BKZ 2.0: Better Lattice Security Estimates|url = https://link.springer.com/chapter/10.1007/978-3-642-25385-0_1|publisher = Springer Berlin Heidelberg|date = 2011|isbn = 978-3-642-25384-3|pages = 1–20|series = Lecture Notes in Computer Science|first = Yuanmi|last = Chen|first2 = Phong Q.|last2 = Nguyen|editor-first = Dong Hoon|editor-last = Lee|editor-first2 = Xiaoyun|editor-last2 = Wang}}</ref> According to the BKZ 2.0 algorithm the key exchange parameters listed above will provide greater than 128 or 256 bits of security, respectively.

==Implementations==