Jump to content

Ring learning with errors

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Cryptocat (talk | contribs) at 21:28, 5 March 2015 (Created page with '{{User sandbox}} <!-- EDIT BELOW THIS LINE --> Digital Signatures are a crucial element of security on the Internet. They are u...'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

This sandbox is in the article namespace. Either move this page into your userspace, or remove the {{User sandbox}} template.

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[1] and further refined by Guneysu, Lybashevsky, and Poppleman also in 2012.[2].

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.[3] 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[1]. 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

  • Rn,q be the ring of degree n-1 polynomials with coefficients in Fq where q is a prime power
  • a be a fixed publicly known polynomial in Rn,q
  • s1 be a randomly chosen secret polynomial in Rn,q
  • s2 be a randomly chosen secret polynomial in Rn.q with coefficients in the set (-1,0,1)
  • s1 and s2 be the long term private signing key
  • t = (a)(s1)+s2 be the long term public key for verification
  • r1 be a randomly chosen secret polynomial in Rn,q
  • r2 be a randomly chosen secret polynomial in Rn,q with coefficients in the set (-1,0,1)
  • r1 and r2 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, s1, and s2. To sign a message (m) expresses as a string, the signer does the following:

  • Randomly generate polynomials r1 and r2 as described above
  • Compute w = (a)(r1)+r2
  • Express w as a string and compute c = H(w,m)
  • Compute z1 = (s1)(c)+r1
  • Compute z2 = (s2)(c)+r2
  • If either z1 or z2 have coefficients outside the range -(k-32) to +(k+32) reject the signature and generate new values for r1 and r2

If z1 and z2 have coefficients in the correct range, accept the polynomials, c, z1, and z2 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, z1 and z2
  • Compute c' = H( ( (a)(z1) + z2 - (t)(c) ), m)
  • Check that c' = c. If not reject the signature.
  • Check that z1 and z2 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)(z1)+z2 - (t)(c) = (a)[(s1)(c)+r1)] + (s2)(c)+r2 - [(a)(s1)+s2](c)

= [(a)(s1)(c)]+[(a)(r1)+r2]+[(s2)(c)]-[(a)(s1)(c)]-[(s2)(c)]

= (a)(r1)+r2

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

c' = H([(a)(r1)+r2], 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 z1 and z2 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 214 or 215 for (n=512,log2(q)=23) or (n=1024,log2(q)=24). The authors claim this provides 100 bits of security.

Other Ring-LWE Signatures

References

  1. ^ a b Lyubashevsky, Vadim (1 October 2011). "Lattice Signature without Trapdoors". Cryptology ePrint Archive. IACR. Retrieved 1 March 2015.
  2. ^ Gunesyu, Tim; Lyubashevsky (2012). "Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems". International Association for Cryptologic Research. IACR. Retrieved 1 March 2015.
  3. ^ Regev, Oded (2005). "On lattices, learning with errors, random linear codes, and cryptography". ACM Digital Library. ACM. Retrieved 1 March 2015.