Ring learning with errors: Difference between revisions

Revision as of 17:10, 8 January 2019

Revision as of 17:12, 8 January 2019

Line 3:

== Background ==

The security of modern cryptography, in particular [[public-key cryptography]], is based on the assumed intractability of solving certain computational problems if the size of the problem is large enough and the instance of the problem to be solved is chosen randomly. The classic example that has been used since the 1970s is the [[integer factorization]] problem. It is believed that it is computationally intractable to factor the product of two prime numbers if those prime numbers are large enough and chosen at random.<ref>{{cite conference |url=https://ieeexplore.ieee.org/document/365700 |title=Algorithms for quantum computation: discrete logarithms and factoring |first=Peter |last=Shor |date=20 November 1994 |conference=35th Annual Symposium on Foundations of Computer Science |publisher=IEEE |archive-date=066 August 2002 |___location=Santa Fe |isbn=0-8186-6580-7 |doi=10.1109/SFCS.1994.365700 |access-date=8 January 2019 |quote="This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems."}}</ref> As of 2015 research has led to the factorization of the product of two 384-bit primes but not the product of two 512-bit primes. [[Integer factorization]] forms the basis of the widely used [[RSA (cryptosystem)|RSA]] cryptographic algorithm.

The ring learning with errors (RLWE) problem is built on the arithmetic of [[polynomials]] with coefficients from a [[finite field]].<ref name=":0" /> A typical polynomial <math display="inline">a(x)</math> is expressed as: