Ring learning with errors

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 lattices. This article is about a provably secure digital signature based on a particular form of lattice problems known as "Ring Learning with Errors" or Ring-LWE. The basic algorithm is due to Lyubashevsky in 2011 and further refined by Guneysu, Lybashevsky, and Poppleman also in 2012..

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 problem was introduced by Regev in 2005. 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" In this paper he discussed the possibility of making the signatures smaller and more efficient by working over a ring of polynomials. It is this algorithm which is described below.

The signature algorithm presented below has a provable reduction to the Short Integer Solution problem for Ideal Lattices. This provable reduction makes the signature an attractive candidate for future standardization.

Lyubashevsky and others have done further research on lattice and Ring-LWE signatures but while providing more efficiency they (to date) lack a proof that their security is reducible to a well known hard mathematical problem. Some of those schemes are outlined in the sections call Non-Provable schemes below.

Provably Secure Ring-LWE Signature (PSRS)

Provably Secure Ring-LWE Signature (PSRS)

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 closely and let q be prime and n will be a power of 2.

Definitions:

Let

• R_n,q be the ring of degree n-1 polynomials with coefficients in F_q where q is a prime power
• a be a fixed publicly known polynomial in R_n,q
• s₁ be a randomly chosen secret polynomial in R_n,q
• s₂ be a randomly chosen secret polynomial in R_n.q with coefficients in the set (-1,0,1)
• 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_n,q
• r₂ be a randomly chosen secret polynomial in R_n,q with coefficients in the set (-1,0,1)
• 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 Rn,q with the property that all but 32 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-32 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-32) and +(k+32). 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-32) to +(k+32) 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.