Ring learning with errors: Difference between revisions

Revision as of 17:43, 7 March 2015

Latest revision as of 19:28, 17 May 2025

(110 intermediate revisions by 54 users not shown)

Line 1:

{{short description|Computational problem possibly useful for post-quantum cryptography}}

{{User sandbox}}

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.

<!-- EDIT BELOW THIS LINE -->

RLWE is more properly called ''learning with errors over rings'' and is simply the larger [[learning with errors]] (LWE) problem specialized to [[polynomial 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| s2cid=8123895 }}</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 a version of the [[shortest vector problem]] (SVP) in a lattice (a polynomial-time reduction from this SVP problem to the RLWE problem has been presented<ref name=":0" />).

[[Digital Signature Algorithm|Digital Signatures]] are a crucial element of security on the Internet. They are used to verify the identities of online entities and to verify the integrity of software and information exchanged over the internet. However, the current digital signature algorithms used on the internet ([[RSA]] or [[Elliptic Curve Cryptography]]) will become insecure if sufficiently large [[quantum computers]] are ever built. One approach to creating a digital signature algorithm that remains secure even when attackers have a quantum computer is based on [[lattice|lattices]]. This article is about a [[Provable security|provably secure]] digital signature based on a particular form of lattice problems known as "Ring [[Learning with errors|Learning with Errors]]" or Ring-LWE. The basic algorithm drawn from Lyubashevsky's 2011 paper, "Lattice Signatures Without Trapdoors." It is further refined by Guneysu, Lybashevsky, and Poppleman in 2012 and Singh in 2015.<ref name=":0">{{Cite web|url = https://eprint.iacr.org/2011/537|title = Lattice Signature without Trapdoors|date = 1 October 2011|accessdate = 1 March 2015|website = Cryptology ePrint Archive|publisher = IACR|last = Lyubashevsky|first = Vadim}}</ref><ref name=":1">{{Cite web|url = http://www.iacr.org/cryptodb/data/paper.php?pubkey=24396|title = Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|date = 2012|accessdate = 1 March 2015|website = International Association for Cryptologic Research|publisher = IACR|last = Gunesyu|first = Tim|last2 = Lyubashevsky|authorlink = Poppleman}}</ref><ref name=":2">{{Cite web|url = https://eprint.iacr.org/2015/138|title = A Practical Key Exchange for the Internet using Lattice Cryptography|date = 19 February 2015|accessdate = 5 March 2015|website = Cryptology ePrint Archive|publisher = IACR|last = Singh|first = Vikram}}</ref>.

== IntroductionBackground ==

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 |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 |___location=Santa Fe |isbn=0-8186-6580-7 |doi=10.1109/SFCS.1994.365700 |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.

There are a number of digital signature algorithms based on the Learning with Errors problem over Rings. The mathematical foundations of the [[Learning with errors|Learning with Errors]] problem was introduced by Regev in 2005.<ref>{{Cite web|url = http://dl.acm.org/citation.cfm?id=1060590.1060603|title = On lattices, learning with errors, random linear codes, and cryptography|date = 2005|accessdate = 1 March 2015|website = ACM Digital Library|publisher = ACM|last = Regev|first = Oded}}</ref> The theory of signatures based on the Learning with Errors problem was developed further by Regev, Peikert and Lyubashevsky. In 2012 Lyubashevsky published "Lattice Signatures without Trapdoors." It is this algorithm, the Trapdoor Free Lattice Signature, which is described below. The signature algorithm presented below has a provable reduction to the Short Integer Solution problem for [[Ideal lattice cryptography|Ideal Lattices]]<ref name=":0" />. This provable reduction makes the signature an attractive candidate for future standardization.

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:

Researchers have created other lattice based signatures after Lyubashevsky's work.<ref>{{Cite web|url = https://eprint.iacr.org/2013/383|title = Lattice Signatures and Bimodal Gaussians|date = 10 December 2013|accessdate = 5 March 2015|website = Cryptology ePrint Archive|publisher = IACR|last = Ducas|first = Leo}}</ref> While they are somewhat more efficient than Lyubashevsky's Trapdoor Free Signature, they lack a security reduction to the worst case instances of a known hard problem. Some of these are closely related to the [[NTRU|NTRU public key system]] and its unprovable security assumptions.

:<math>a(x) = a_0 + a_1x + a_2x^2 + \ldots + a_{n-2}x^{n-2} + a_{n-1}x^{n-1}</math>

== Trapdoor Free Lattice Signature (TFLS) ==

Polynomials can be added and multiplied in the usual fashion. In the RLWE context the coefficients of the polynomials and all operations involving those coefficients will be done in a finite field, typically the field <math display="inline">\mathbf{Z}/q\mathbf{Z} = \mathbf{F}_q</math> for a prime integer <math display="inline">q</math>. The set of polynomials over a finite field with the operations of addition and multiplication forms an infinite [[polynomial ring]] (<math display="inline">\mathbf{F}_q[x]</math>). The RLWE context works with a finite quotient ring of this infinite ring. The quotient ring is typically the finite [[Quotient ring|quotient (factor) ring]] formed by reducing all of the polynomials in <math display="inline">\mathbf{F}_q[x]</math> modulo an [[irreducible polynomial]] <math display="inline">\Phi(x)</math>. This finite quotient ring can be written as <math>\mathbf{F}_q[x]/\Phi(x)</math> though many authors write <math>\mathbf{Z}_q[x]/\Phi(x)</math> .<ref name=":0" />

In this signature algorithm, we will be working in a ring (R) of polynomials of degree n with coefficients in the finite field Fq. We will follow the work of Gunesyu, Lyubashevsy, and Poppleman<ref name=":1" /> as well as that of Singh<ref name=":2" /> closely. Let q be prime and n be a power of 2.

If the degree of the polynomial <math>\Phi(x)</math> is <math display="inline">n</math>, the quotient ring becomes the ring of polynomials of degree less than <math>n</math> modulo <math>\Phi(x)</math> with coefficients from <math>F_q</math>. The values <math display="inline">n</math>, <math display="inline">q</math>, together with the polynomial <math>\Phi(x)</math> partially define the mathematical context for the RLWE problem.

=== Definitions: ===

Let

* R be the ring of polynomials with degree less than n and with coefficients in F_q with q a prime.

* a be a fixed publicly known polynomial in R

* b be an integer less than q which serves as a bound for polynomial coefficients over the integers

* s₁ be a randomly chosen secret polynomial in R with coefficients chosen between (-b) and (+b)

* s₂ be a randomly chosen secret polynomial in R with coefficients chosen between (-b) and (+b)

* the bounded polynomials s₁ and s₂ be the long term private signing key

* t = (a)(s₁)+s₂ be the long term public key for verification

* r₁ be a randomly chosen secret polynomial in R with coefficients chosen between (-b) and (+b)

* r₂ be a randomly chosen secret polynomial in R with coefficients chosen between (-b) and (+b)

* the bounded polynomials r₁ and r₂ be the short term (per signature) private signing key

Another concept necessary for the RLWE problem is the idea of "small" polynomials with respect to some norm. The typical norm used in the RLWE problem is known as the infinity norm (also called the [[uniform norm]]). The infinity norm of a polynomial is simply the largest coefficient of the polynomial when these coefficients are viewed as integers. Hence, <math>||a(x)||_\infty = b</math> states that the infinity norm of the polynomial <math>a(x)</math> is <math>b</math>. Thus <math>b</math> is the largest coefficient of <math>a(x)</math>.

* H(a,b) be a hash function which maps strings a and b to polynomials in R with the property that all but j coefficients are 0 and the remaining coefficients are either 1 or -1.

The final concept necessary to understand the RLWE problem is the generation of random polynomials in <math>\mathbf{F}_q[x]/\Phi(x)</math> and the generation of "small" polynomials . A random polynomial is easily generated by simply randomly sampling the <math>n</math> coefficients of the polynomial from <math>\mathbf{F}_q</math>, where <math>\mathbf{F}_q</math> is typically represented as the set <math>\{-(q-1)/2, ..., -1, 0, 1, ..., (q-1)/2\}</math>.

Another parameter, an integer k, will be crucial to the security of the signatures scheme. Related to the definition of the hash function H(a,b), k will be chosen so that k-j will define an "acceptance bound" for the polynomials created as the signature of the message. The coefficients of the signature polynomial will need to be between -(k-j) and +(k+j). If the coefficients of the computed polynomials are not in this range, the signature is "rejected" and the signing process starts over. This process is known as rejection sampling.

Randomly generating a "small" polynomial is done by generating the coefficients of the polynomial from <math>\mathbf{F}_q</math> in a way that either guarantees or makes very likely small coefficients. When <math>q</math> is a prime integer, there are two common ways to do this:

=== Signature Generation: ===

# Using Uniform Sampling – The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let <math display="inline">b</math> be an integer that is much less than <math display="inline">q</math>. If we randomly choose coefficients from the set: <math display="inline">\{ -b, -b+1, -b+2, \ldots , -2, -1, 0, 1, 2, \ldots , b-2, b-1, b \}</math> the polynomial will be small with respect to the bound (<math display="inline">b</math>).

The message signer holds a, s₁, and s₂. To sign a message (m) expresses as a string, the signer does the following:

# Using [[Gaussian_function#Discrete_Gaussian|discrete Gaussian sampling]] – For an odd value for <math display="inline">q</math>, the coefficients of the polynomial are randomly chosen by sampling from the set <math display="inline"> \{ -(q-1)/2, \ldots , (q-1)/2 \} </math> according to a discrete Gaussian distribution with mean <math>0</math> and distribution parameter <math display="inline">\sigma</math>. The references describe in full detail how this can be accomplished. It is more complicated than uniform sampling but it allows for a proof of security of the algorithm. The paper "Sampling from Discrete Gaussians for Lattice-Based Cryptography on a Constrained Device" by Dwarakanath and Galbraith provides an overview of this problem.<ref>{{Cite journal|title = Sampling from discrete Gaussians for lattice-based cryptography on a constrained device|journal = Applicable Algebra in Engineering, Communication and Computing|date = 2014-03-18|issn = 0938-1279|pages = 159–180|volume = 25|issue = 3|doi = 10.1007/s00200-014-0218-3|first1 = Nagarjun C.|last1 = Dwarakanath|first2 = Steven D.|last2 = Galbraith|s2cid = 13718364|citeseerx = 10.1.1.716.376}}</ref>

== The RLWE problem ==

* Randomly generate polynomials r₁ and r₂ as described above

The RLWE problem can be stated in two different ways: a "search" version and a "decision" version. Both begin with the same construction. Let

* Compute w = (a)(r₁)+r₂

* <math>a_i(x)</math> be a set of random but '''known''' polynomials from <math>\mathbf{F}_q[x]/\Phi(x)</math> with coefficients from all of <math>\mathbf{F}_q</math>.

* Express w as a string and compute c = H(w,m)

* <math>e_i(x)</math> be a set of small random and '''unknown''' polynomials relative to a bound <math>b</math> in the ring <math>\mathbf{F}_q[x]/\Phi(x)</math>.

* Compute z₁ = (s₁)(c)+r₁

* <math>s(x)</math> be a small '''unknown''' polynomial relative to a bound <math>b</math> in the ring <math>\mathbf{F}_q[x]/\Phi(x)</math>.

* Compute z₂ = (s₂)(c)+r₂

* <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math>.

* If either z₁ or z₂ have coefficients outside the range -(k-j) to +(k+j) reject the signature and generate new values for r₁ and r₂

The Search version entails finding the unknown polynomial <math>s(x)</math> given the list of polynomial pairs <math>( a_i(x), b_i(x) )</math>.

If z₁ and z₂ have coefficients in the correct range, accept the polynomials, c, z₁, and z₂ as the signature and transmit them, along with the message, to the verifier.

The Decision version of the problem can be stated as follows. Given a list of polynomial pairs <math>( a_i(x), b_i(x) )</math>, determine whether the <math>b_i(x)</math> polynomials were constructed as <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math> or were generated randomly from <math>\mathbf{F}_q[x]/\Phi(x)</math> with coefficients from all of <math>\mathbf{F}_q</math>.

=== Signature Verification: ===

The signature verifier has the polynomials a and the public key t for a particular signer. To verify that a message (m) came from that signer, the verifier does the following:

* Receive the signature on m consisting of c, z₁ and z₂

* Compute c' = H( ( (a)(z₁) + z₂ - (t)(c) ), m)

* Check that c' = c. If not reject the signature.

* Check that z₁ and z₂ have coefficients in the proper range (noted above).

* If the coefficients are in the range, accept the signature . Otherwise reject the signature.

The difficulty of this problem is parameterized by the choice of the quotient polynomial (<math>\Phi(x)</math>), its degree (<math>n</math>), the field (<math>\mathbf{F}_q</math>), and the smallness bound (<math>b</math>). In many RLWE based public key algorithms the private key will be a pair of small polynomials <math>s(x)</math> and <math>e(x)</math>. The corresponding public key will be a pair of polynomials <math>a(x)</math>, selected randomly from <math>\mathbf{F}_q[x]/\Phi(x)</math>, and the polynomial <math>t(x)= (a(x)\cdot s(x)) + e(x)</math>. Given <math>a(x)</math> and <math>t(x)</math>, it should be computationally infeasible to recover the polynomial <math>s(x)</math>.

Note the following:

== Security reduction ==

(a)(z₁)+z₂ - (t)(c) = (a)[(s₁)(c)+r₁)] + (s₂)(c)+r₂ - [(a)(s₁)+s₂](c)

The difficulty of solving the search version of RLWE problem is equivalent to finding a short vector (but not necessarily the shortest vector) in an ideal lattice formed from elements of <math>\mathbf{Z}[x]/\Phi(x)</math> represented as integer vectors.<ref name=":0">{{Cite journal|title = On Ideal Lattices and Learning with Errors Over Rings|url = http://eprint.iacr.org/2012/230|date = 2012|first1 = Vadim|last1 = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev| journal=Cryptology ePrint Archive }}</ref> This problem is commonly known as the [[Shortest vector problem|Approximate Shortest Vector Problem (α-SVP)]] and it is the problem of finding a vector shorter than α times the shortest vector. The authors of the proof for this equivalence write:

:''"... we give a quantum reduction from approximate SVP (in the worst case) on ideal lattices in <math>\mathbf{R}</math> to the search version of ring-LWE, where the goal is to recover the secret <math>s \in \mathbf{R}_q</math> (with high probability, for any <math>s</math>) from arbitrarily many noisy products."''<ref name=":0" />

= [(a)(s₁)(c)]+[(a)(r₁)+r₂]+[(s₂)(c)]-[(a)(s₁)(c)]-[(s₂)(c)]

In that quote, The ring <math>\mathbf{R}</math> is <math>\mathbf{Z}[x]/\Phi(x)</math> and the ring <math>\mathbf{R}_q</math> is <math>\mathbf{F}_q[x]/\Phi(x)</math>.

= (a)(r₁)+r₂

The α-SVP in regular lattices is known to be [[NP-hard]] due to work by Daniele Micciancio in 2001, although not for values of α required for a reduction to general learning with errors problem.<ref name=":1">{{Cite journal|title = The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant|journal = SIAM Journal on Computing|date = January 1, 2001|issn = 0097-5397|pages = 2008–2035|volume = 30|issue = 6|doi = 10.1137/S0097539700373039|first = D.|last = Micciancio|citeseerx = 10.1.1.93.6646}}</ref> However, there is not yet a proof to show that the difficulty of the α-SVP for ideal lattices is equivalent to the average α-SVP. Rather we have a proof that if there are ''any'' α-SVP instances that are hard to solve in ideal lattices then the RLWE Problem will be hard in random instances.<ref name=":0" />

Thus, if m' is the received message, we compute:

Regarding the difficulty of Shortest Vector Problems in Ideal Lattices, researcher Michael Schneider writes, ''"So far there is no SVP algorithm making use of the special structure of ideal lattices. It is widely believed that solving SVP (and all other lattice problems) in ideal lattices is as hard as in regular lattices."''<ref>{{Cite journal|title = Sieving for Shortest Vectors in Ideal Lattices|url = http://eprint.iacr.org/2011/458|date = 2011|first = Michael|last = Schneider| journal=Cryptology ePrint Archive }}</ref> The difficulty of these problems on regular lattices is provably [[NP-hard]].<ref name=":1" /> There are, however, a minority of researchers who do not believe that ideal lattices share the same security properties as regular lattices.<ref>{{Cite web|title = cr.yp.to: 2014.02.13: A subfield-logarithm attack against ideal lattices|url = http://blog.cr.yp.to/20140213-ideal.html|website = blog.cr.yp.to|access-date = 2015-07-03}}</ref>

c' = H([(a)(r₁)+r₂], m')

Peikert believes that these security equivalences make the RLWE problem a good basis for future cryptography. He writes: ''"There is a mathematical proof that the'' ''only'' ''way to break the cryptosystem (within some formal attack model) on its random instances is by being able to solve the underlying lattice problem in the'' ''worst case"'' (emphasis in the original).<ref>{{Cite web |title = What does GCHQ's "cautionary tale" mean for lattice cryptography? |url = http://web.eecs.umich.edu/~cpeikert/soliloquy.html |website = www.eecs.umich.edu|access-date = 2016-01-05 |archive-url = https://web.archive.org/web/20160317165656/http://web.eecs.umich.edu/~cpeikert/soliloquy.html |archive-date = 2016-03-17}}</ref>

If the received message is the same as that signed, c'=c.

== RLWE cryptography ==

As Guneysu, Lyubashevsky, and Poppleman (GLP) state in their paper the choice of the value k is critical to the security of the scheme. If key is too small then the coefficients of the z₁ and z₂ polynomials almost never fall in the proper range and signing takes a incredibly long time. If k is too big there exists a forgery attack on the signature. In their paper, GLP recommend k's as either 2¹⁴ or 2¹⁵ for (n=512,log₂(q)=23) or (n=1024,log₂(q)=24). The authors claim this provides 100 bits of security.

A major advantage that RLWE based cryptography has over the original learning with errors (LWE) based cryptography is found in the size of the public and private keys. RLWE keys are roughly the square root of keys in LWE.<ref name=":0" /> For 128 [[bits of security]] an RLWE cryptographic algorithm would use public keys around 7000 bits in length.<ref>{{Cite journal|title = A Practical Key Exchange for the Internet using Lattice Cryptography|url = http://eprint.iacr.org/2015/138|date = 2015|first = Vikram|last = Singh| journal=Cryptology ePrint Archive }}</ref> The corresponding LWE scheme would require public keys of 49 million bits for the same level of security.<ref name=":0" />{{failed verification|date=August 2016}} On the other hand, RLWE keys are larger than the keys sizes for currently used public key algorithms like RSA and Elliptic Curve Diffie-Hellman which require public [[key size]]s of 3072 bits and 256 bits, respectively, to achieve a 128-bit level of security. From a computational standpoint, however, RLWE algorithms have been shown to be the equal of or better than existing public key systems.<ref>{{Cite journal|title = Efficient Software Implementation of Ring-LWE Encryption|url = http://eprint.iacr.org/2014/725|date = 2014|first = Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid|last = Verbauwhede| journal=Cryptology ePrint Archive }}</ref>

Three groups of RLWE cryptographic algorithms exist:

== Other Ring-LWE Signatures ==

=== Ring learning with errors key exchanges (RLWE-KEX) ===

== References ==

{{main|Ring learning with errors key exchange}}

<references />

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|last1=Ding|first1=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|journal=Cryptology ePrint Archive |url=http://eprint.iacr.org/2012/688}}</ref> appeared in 2012 after a provisional patent application was filed in 2012.

In 2014, Peikert<ref>{{Cite journal|last=Peikert|first=Chris|date=2014-01-01|title=Lattice Cryptography for the Internet|journal=Cryptology ePrint Archive |url=http://eprint.iacr.org/2014/070}}</ref> presented a key transport scheme following the same basic idea of Ding's, where the new idea of sending additional 1 bit signal for rounding in Ding's construction 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|first1 = Jiang|last1 = Zhang|first2 = Zhenfeng|last2 = Zhang|first3 = Jintai|last3 = Ding|first4 = Michael|last4 = Snook|first5 = Özgür|last5 = Dagdelen| journal=Cryptology ePrint Archive }}</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 (RLWE-SIG) ===

{{main|Ring learning with errors signature}}

A RLWE version of the classic [[Feige–Fiat–Shamir identification scheme|Feige–Fiat–Shamir Identification protocol]] was created and converted to a digital signature in 2011 by Lyubashevsky.<ref>{{Cite journal|title = Lattice Signatures Without Trapdoors|url = http://eprint.iacr.org/2011/537|date = 2011|first = Vadim|last = Lyubashevsky| journal=Cryptology ePrint Archive }}</ref> The details of this signature were extended in 2012 by Gunesyu, Lyubashevsky, and Popplemann in 2012 and published in their paper "Practical Lattice Based Cryptography – A Signature Scheme for Embedded Systems."<ref>{{Cite book|title = Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|publisher = Springer Berlin Heidelberg|date = 2012|isbn = 978-3-642-33026-1|pages = 530–547|series = Lecture Notes in Computer Science|first1 = Tim|last1 = Güneysu|first2 = Vadim|last2 = Lyubashevsky|first3 = Thomas|last3 = Pöppelmann|editor-first = Emmanuel|editor-last = Prouff|editor-first2 = Patrick|editor-last2 = Schaumont|doi = 10.1007/978-3-642-33027-8_31}}</ref> These papers laid the groundwork for a variety of recent signature algorithms some based directly on the ring learning with errors problem and some which are not tied to the same hard RLWE problems.<ref>{{Cite web|title = BLISS Signature Scheme|url = http://bliss.di.ens.fr/|website = bliss.di.ens.fr|access-date = 2015-07-04}}</ref>

=== Ring learning with errors homomorphic encryption (RLWE-HOM) ===

{{main|Homomorphic encryption}}

Homomorphic encryption is type of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The purpose of homomorphic encryption is to allow the computations on sensitive data to occur on computing devices that should not be trusted with the data. These computing devices are allowed to process the ciphertext which is output from a homomorphic encryption. In 2011, Brakersky and Vaikuntanathan, published "Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages" which builds a homomorphic encryption scheme directly on the RLWE problem.<ref>{{Cite book|title = Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages|publisher = Springer Berlin Heidelberg|date = 2011|isbn = 978-3-642-22791-2|pages = 505–524|series = Lecture Notes in Computer Science|first1 = Zvika|last1 = Brakerski|first2 = Vinod|last2 = Vaikuntanathan|editor-first = Phillip|editor-last = Rogaway|doi = 10.1007/978-3-642-22792-9_29}}</ref>

==References==

{{Reflist|30em}}

{{Computational hardness assumptions}}

[[Category:Computational problems]]

[[Category:Computational hardness assumptions]]

[[Category:Post-quantum cryptography]]

[[Category:Lattice-based cryptography]]