Ring learning with errors: Difference between revisions

Revision as of 17:47, 7 March 2015

Revision as of 17:48, 7 March 2015

Line 1:

{{User sandbox}}

<!-- EDIT BELOW THIS LINE -->

[[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>.

== Introduction ==

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.

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.

== Ring-LWE Signature (RLS) ==

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.

=== 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

* 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.

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.

=== Signature Generation: ===

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

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

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

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

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

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

* 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₂

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.

=== 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.

Note the following:

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

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

= (a)(r₁)+r₂

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

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

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

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.

== Other Ring-LWE Signatures ==

== References ==

<references />