Ring learning with errors: Difference between revisions

Revision as of 11:49, 25 October 2017

Revision as of 13:23, 13 December 2017

Line 1:

{{technical|date=September 2015}}

'''Ring learning with errors''' ('''RLWE''') is a [[computational problem]] which serves as the foundation of new cryptographic [[algorithm]]s designed to protect against [[cryptanalysis]] by [[quantum computers]] and also to provide the basis for [[homomorphic encryption]]. RLWE is more properly called Learning with Errors over Rings and is simply the larger [[learning with errors]] (LWE) problem specialized to [[polynomial rings]] over finite fields.<ref name=":0" /> Because of the presumed difficulty of solving the RLWE problem even on a quantum computer, RLWE based cryptography may form the fundamental base for [[public-key cryptography]] in the future just as the [[integer factorization]] and [[discrete logarithm]] problem have served as the base for public key cryptography since the early 1980s.<ref name=":2">{{Cite book|title = Lattice Cryptography for the Internet|url = https://link.springer.com/chapter/10.1007/978-3-319-11659-4_12|publisher = Springer International Publishing|isbn = 978-3-319-11658-7|pages = 197–219|series = Lecture Notes in Computer Science|first = Chris|last = Peikert|editor-first = Michele|editor-last = Mosca}}</ref> An important feature of basing cryptography on the ring learning with errors problem is the fact that the solution to the RLWE problem may be reducible to the [[NP-hard|NP-Hard]] [[Shortestshortest vector problem|Shortest Vector Problem]] (SVP) in a Latticelattice.<ref name=":0" />

== Background ==