Ring learning with errors key exchange: Difference between revisions

Revision as of 14:18, 28 August 2023

Latest revision as of 23:09, 30 August 2024

(2 intermediate revisions by 2 users not shown)

Line 37:

== 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 <math> R_q = ZqZ_q[x]/\Phi(x)</math>. 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 89:

== Key exchange security ==

The security of this key exchange is based on the underlying hardness of [[ring learning with errors]] problem that has been proven to be as hard as the worst case solution to the [[shortest vector problem]] (SVP) in an [[ideal lattice cryptography|ideal lattice]].<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|publisher = Springer Berlin Heidelberg|date = 2011|isbn = 978-3-642-25384-3|pages = 1–20|series = Lecture Notes in Computer Science|first1 = Yuanmi|last1 = Chen|first2 = Phong Q.|last2 = Nguyen| title=Advances in Cryptology – ASIACRYPT 2011 | chapter=BKZ 2.0: Better Lattice Security Estimates | volume=7073 |editor-first = Dong Hoon|editor-last = Lee|editor-first2 = Xiaoyun|editor-last2 = Wang|doi = 10.1007/978-3-642-25385-0_1}}</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==

Line 95:

== Other approaches ==

A variant of the approach described above is an authenticated version in the work of Zhang, Zhang, Ding, Snook and Dagdelen in their paper, "Post Quantum Authenticated Key Exchange from Ideal Lattices."<ref>{{Cite journal|title = Workshop on Cybersecurity in a Post-Quantum World|url = https://www.nist.gov/itl/csd/ct/post-quantum-crypto-workshop-2015.cfm|journal = NIST|access-date = 2015-06-06|date = 2015-04-02}}</ref> 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."<ref>{{Cite web|title = Noisy Diffie–Hellman protocols|url = https://pqc2010.cased.de/rr/03.pdf|website = pqc2010.cased.de|access-date = 2015-06-06|archive-url=https://web.archive.org/web/20150614110435/https://pqc2010.cased.de/rr/03.pdf |archive-date=2015-06-14 |url-status=dead}}</ref>

In November 2015, Alkim, Ducas, Pöppelmann, and Schwabe built on the prior work of Peikert and used what they believe is a more conservative costing of lattice attacks to recommend parameters.<ref name=":3">{{Cite web|title = Cryptology ePrint Archive: Report 2015/1092|url = https://eprint.iacr.org/2015/1092|website = eprint.iacr.org|access-date = 2015-11-11}}</ref> Software based on the work of Alkim, Ducas, Pöppelmann, and Schwabe is found on GitHub at https://github.com/tpoeppelmann/newhope<ref name=":3" />