Revision as of 17:29, 6 November 2021 edit TJKS (talk \| contribs) 4 edits →Background: Added condition to example methods to avoid confusion. When <math>q=p^n</math>, the elements of <math>F_q</math>, are not necessarily residues of integers. In such a circumstance ordering them linearly doesn’t make sense, and the iterative notation of the example means of generating “small” coefficients is incoherent. By adding the condition that <math>q</math> is a prime integer, that incoherence is excluded from consideration. Tags: Mobile edit Mobile web edit ← Previous edit		Revision as of 19:43, 15 April 2022 edit undo 2601:541:4580:8500:7123:4c18:6d5a:ca95 (talk) change link Next edit →
Line 3: In [[post-quantum cryptography]], '''ring learning with errors''' ('''RLWE''') is a [[computational problem]] which serves as the foundation of new cryptographic [[algorithm]]s, such as [[NewHope]], designed to protect against [[cryptanalysis]] by [[quantum computers]] and also to provide the basis for [[homomorphic encryption]]. [[Public-key cryptography]] relies on construction of mathematical problems that are believed to be hard to solve if no further information is available, but are easy to solve if some information used in the problem construction is known. Some problems of this sort that are currently used in cryptography are at risk of attack if sufficiently large quantum computers can ever be built, so resistant problems are sought. Homomorphic encryption is a form of encryption that allows computation on ciphertext, such as arithmetic on numeric values stored in an encrypted database. RLWE is more properly called ''learning with errors over rings'' and is simply the larger [[learning with errors]] (LWE) problem specialized to [[polynomial ~~rings~~ring]]s 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\|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\|doi = 10.1007/978-3-319-11659-4_12\|title = Post-Quantum Cryptography\|volume = 8772\|year = 2014\|chapter = Lattice Cryptography for the Internet\|citeseerx = 10.1.1.800.4743}}</ref> An important feature of basing cryptography on the ring learning with errors problem is the fact that the solution to the RLWE problem can be used to solve the [[NP-hard]] [[shortest vector problem]] (SVP) in a lattice (a polynomial-time reduction from the SVP problem to the RLWE problem has been presented<ref name=":0" />). == Background ==

Ring learning with errors: Difference between revisions