Ring learning with errors: Difference between revisions

Revision as of 21:04, 6 September 2016

Revision as of 03:55, 21 September 2016

Line 57:

=== [[Ring learning with errors key exchange|Ring Learning with Errors Key Exchanges]] (RLWE-KEX) ===

The fundamental idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The basic idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper<ref>{{Cite journal|last=Ding|first=Jintai|last2=Xie|first2=Xiang|last3=Lin|first3=Xiaodong|date=2012-01-01|title=A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem|url=http://eprint.iacr.org/2012/688|journal=|volume=|issue=|doi=|pmid=|access-date=|via=}}</ref> appeared in 2012 after a provisional patent application was filed in 2012.

A RLWE version of the classic Diffie-Hellman key exchange was designed by Peikert and published in early 2014.<ref name=":2" /> An RLWE version of the classic MQV variant of a Diffie-Hellman key exchange was later published by Zhang et al.<ref>{{Cite journal|title = Authenticated Key Exchange from Ideal Lattices|url = http://eprint.iacr.org/2014/589|date = 2014|first = Jiang|last = Zhang|first2 = Zhenfeng|last2 = Zhang|first3 = Jintai|last3 = Ding|first4 = Michael|last4 = Snook|first5 = Özgür|last5 = Dagdelen}}</ref> The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice.

AIn RLWE2014, versionPeikert<ref>{{Cite journal|last=Peikert|first=Chris|date=2014-01-01|title=Lattice Cryptography for of the classic DiffieInternet|url=http://eprint.iacr.org/2014/070|journal=|volume=|issue=|doi=|pmid=|access-Hellmandate=|via=}}</ref> presented a key exchangetransport wasscheme designedfollowing bythe Peikertsame andbasic publishedidea of Ding's, where the new idea of sending additional 1 bit signal for rounding in earlyDing's 2014.<refconstruction name=":2"is />also utilized. An RLWE version of the classic MQV variant of a Diffie-Hellman key exchange was later published by Zhang et al.<ref>{{Cite journal|title = Authenticated Key Exchange from Ideal Lattices|url = http://eprint.iacr.org/2014/589|date = 2014|first = Jiang|last = Zhang|first2 = Zhenfeng|last2 = Zhang|first3 = Jintai|last3 = Ding|first4 = Michael|last4 = Snook|first5 = Özgür|last5 = Dagdelen}}</ref> The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice.

=== [[Ring learning with errors signature|Ring Learning with Errors Signatures]] (RLWE-SIG) ===