Wikipedia

Ring learning with errors

This is an old revision of this page, as edited by Cryptocat (talk | contribs) at 17:43, 7 March 2015 (changed notation). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

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.[4] 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 Lattices[1]. This provable reduction makes the signature an attractive candidate for future standardization.

Researchers have created other lattice based signatures after Lyubashevsky's work.[5] 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 public key system and its unprovable security assumptions.

Trapdoor Free Lattice Signature (TFLS)

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[2] as well as that of Singh[3] 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 Fq 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
  • s1 be a randomly chosen secret polynomial in R with coefficients chosen between (-b) and (+b)
  • s2 be a randomly chosen secret polynomial in R with coefficients chosen between (-b) and (+b)
  • the bounded polynomials 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 R with coefficients chosen between (-b) and (+b)
  • r2 be a randomly chosen secret polynomial in R with coefficients chosen between (-b) and (+b)
  • the bounded polynomials 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 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, 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-j) to +(k+j) 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. ^ a b 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. ^ a b Singh, Vikram (19 February 2015). "A Practical Key Exchange for the Internet using Lattice Cryptography". Cryptology ePrint Archive. IACR. Retrieved 5 March 2015.
  4. ^ Regev, Oded (2005). "On lattices, learning with errors, random linear codes, and cryptography". ACM Digital Library. ACM. Retrieved 1 March 2015.
  5. ^ Ducas, Leo (10 December 2013). "Lattice Signatures and Bimodal Gaussians". Cryptology ePrint Archive. IACR. Retrieved 5 March 2015.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ring_learning_with_errors&oldid=650321735"