Ring learning with errors signature

• Comment: Amazing beginning but just not there yet. --Anarchyte 04:03, 23 June 2015 (UTC)

---

Digital Signatures are a means to protect digital information from intentional modification and to authenticate the source of digital information. Public key cryptography provides a rich set of different cryptographic algorithms the create digital signatures. However, all of the public key signatures currently in use will become completely insecure if scientists are ever able to build a large scale quantum computer. Digital signature algorithms such as the Ring learning with errors signature (RLWE-SIG) described in this article is on example of a new class of cryptographic algorithms (Post-quantum cryptography) being designed to resist cryptanalytic attacks run on a quantum computer. Having quantum safe digital signatures designed, analyzed, and available for implementation is important for the long term safety of the internet and electronic commerce.

Introduction

Developments in quantum computing over the past decade and the optimistic prospects for real quantum computers within 20 years have begun to threaten the basic cryptography that secures the internet.  A relatively small quantum computer capable of processing only ten thousand of bits of information would easily break all of the the widely used public key cryptography algorithms used to digitally sign information in computer networks.

The most widely used public key algorithm used to create digital signatures is known as RSA.  Its security is based on the classical difficulty of factoring the product of two large and unknown primes into the constituent primes.  This problem, the integer factorization problem, is believed to be intractable on any conventional computer if the primes are chosen at random and are sufficiently large.  However, to break an RSA key of length n bits, a quantum computer with roughly 3n bits of logical qubit memory and capable of executing a program known as Shor’s algorithm will be able to quickly factor the product of two primes.  Shor's algorithm can also quickly break digital signatures based on what is known as the discrete logarithm problem and the more esoteric elliptic curve discrete logarithm problem. In effect, a relatively small quantum computer running Shor's algorithm can break all of the digital signatures used to ensure the privacy and integrity of information on the internet today.

Even though we do not know when a quantum computer to break RSA will exist, there is active research on cryptographic algorithms which remain secure even when an attacker has the resources of a quantum computer at their disposal.  This new area of cryptography is called Post Quantum or Quantum Safe cryptography.  This article is about one class of these algorithms:  digital signatures based on the Ring Learning with Errors problem.  The use of this problem in cryptography was introduced by Oded Regev in 2005 and has been the source of a rich literature of analysis and cryptographic designs.

An important feature of algorithms based on Ring-Learning with Errors is their provable reduction to known hard problems. The signature described below has a provable reduction to the Shortest Vector Problem in an integer lattice. This means that if an attack can be found on the Ring-LWE cryptosystem then a whole class of presumed hard computational problems will have a solution.

The first RLWE-SIG was developed by Lyubashevsky in his paper "Lattice Signatures Without Trapdoors" in 2011. A number of refinements and variants have followed. This article highlights some features of a RLWE-SIG which closely follows the original Lyubashevsky work and is due to the work of Guneysu, Lyubashevsky and Popplemann (GLP).  A later section of this article provides references to other signatures based on Lyubashevsky's original work.

Background

A RLWE-SIG works in the quotient ring of polynomials modulo a degree n polynomial Φ(x) with coefficients in the ring F_q for an odd prime q ( i.e. the ring F_q[x]/Φ(x) ). Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod Φ(x). For this presentation a typical polynomial is expressed as:

$a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}$

The field F_q has its representative elements in the set { -(q-1)/2, ...-1, 0, 1, ... (q-1)/2 }.

[See the Wikipedia pages on Quotient Rings and Polynomial Rings for further explanation]

Generating "Small" Polynomials.

A RLWE-SIG uses polynomials which are considered "small" with respect to a measure called the "infinity norm." The infinity norm for a polynomial is simply the largest absolute value of the coefficients of the polynomial . The signature algorithm will create random polynomials which are small with respect to a particular infinity norm bound. This is done by randomly generating the coefficients of the polynomial (a₀, ..., a_n-1) which are guaranteed or very likely to be less than or equal to this bound. In the literature on Ring Learning with Errors, there are two common ways to do this:

• Using Uniform Sampling - The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let b be an integer that is much less than q. If we randomly choose polynomial coefficients from the set: { -b, -b+1, -b+2. ... -2, -1, 0, 1, 2, ... , b-2, b-1, b} the infinity norm of the polynomial will be ≤ (b).
• Using Discrete Gaussian Sampling - For an odd integer q, the coefficients are randomly chosen by sampling from the set { -(q-1)/2 to (q-1)/2 } according to a discrete Gaussian distribution with mean 0 and distribution parameter σ. The references provide more details on this method.

In the RLWE-SIG of Gunesyu, Lyubashevsky, and Popplemann used as an example below, coefficients for the "small" polynomials will use the uniform sampling method and the value b will be much smaller than the value q.

Hashing to a "Small" Polynomial

Most RLWE-SIG algorithms also require the ability to cryptographically hash arbitrary bit strings into small polynomials according to some distribution. The example below uses a hash function, HASH(ω), which accepts a bit string, ω, as input and outputs a polynomial with n coefficients such that exactly k of these coefficients are either -1 or 1 and the remaining coefficients are 0. The GLP paper provides details on one way this can be easily done.

Rejection Sampling

An key feature of RLWE-SIG algorithms is the use of a technique known as rejection sampling. In this technique if the infinity norm of a signature polynomial exceeds a fixed bound, β, that polynomial will be discarded and the signing process will begin again. This process will be repeated until the infinity norm of the signature polynomial is less than or equal to the bound. Rejection sampling ensures that the output signature is not exploitably correlated with the signer's secret key values.

In the example which follows, the bound, β, will be (b - k), where b is the range of the uniform sampling described above.

Other Parameters

Following GLP and as noted above, the maximum degree of the polynomials will be n-1 and therefore have n coefficients. Typical values for n are 512, and 1024. The coefficients of these polynomials will be from the field F_q where q is an odd prime congruent to 1 mod 4. For n =512 the authors of GLP set q to be a 22 bit prime and the corresponding b value to be 2¹⁴. For n=1024, GLP sets q to be a 23-bit prime and b to be 2¹⁵. The number of non-zero coefficients produced by the hash function (k) is equal to 32 for both cases. The security of the signature scheme is closely tied to the relative sizes of n, q, b, and k. Details on setting these parameters can be found in references 5 and 6 below.

The polynomial Φ(x) which defines the ring of polynomials used will be xⁿ + 1. Finally, a(x) will be a randomly chosen and fixed polynomial with coefficients from the set { -(q-1)/2 to (q-1)/2 }. All signers and verifiers of signatures will know n, q, b, k, Φ(x), a(x) and β = b-k

Public Key Generation

An entity wishing to sign messages generates its public key through the following steps:

1. Generate two small polynomials s₀(x) and s₁(x) with coefficients chosen uniformly from the set {-1, 0, 1}
2. Compute t(x) = a(x)·s₀(x) + s₁(x)
3. Distribute t(x) as the entity's public key

The polynomials s₀(x) and s₁(x) serve as the private key and t(x) is the corresponding private key. The security of this signature scheme is based on the following problem. Given a polynomial t(x) find small polynomials f₁(x) and f₂(x) such that: a(x)·f₁(x) + f₂(x) = t(x)

If this problem is difficult to solve, then the signature scheme will be will be difficult to forge. [See the Wikipedia article on Ideal Lattice Cryptography for more details on the theoretical difficulty of this problem]

Signature Generation

Following GLP, to sign a message m expressed as a bit string, the signing entity does the following:

1. Generate two small polynomials y₀(x) and y₁(x) with coefficients from the set {-b, ..., 0, ...., b}
2. Compute w(x) = a(x)·y₀(x) + y₁(x)
3. Map w(x) into a bit string ω
4. Compute c(x) = HASH(ω | m) (This is a polynomial with k non-zero coefficients. The "|" denotes concatenation of strings)
5. Compute z₀(x) = s₀(x)·c(x) + y₀(x)
6. Compute z₁(x) = s₁(x)·c(x) + y₁(x)
7. Until the infinity norms of z₀(x) and z₁(x) ≤ β go to step 1. (This is the rejection sampling step noted above)
8. The signature is the triple of polynomials c(x), z₀(x) and z₁(x)
9. Transmit the message along with c(x), z₀(x) and z₁(x) to the verifier.

Signature Verification

Following GLP, to verify a message m expressed as a bit string, the verifying entity must posses the signer's public key (t(x)), the signature (c(x), z₀(x), z₁(x)), and the message m. The verifier does the following:

1. Verify that the infinity norms of z₀(x) and z₁(x) ≤ β , if not reject the signature.
2. Compute w'(x) = a(x)·z₀(x) + z₁(x) - t(x)c(x)
3. Map w'(x) into a bit string ω'
4. Compute c'(x) = HASH(ω' | m)
5. If c'(x) ≠ c(x) reject the signature, otherwise accept the signature as valid.

Notice that:

a(x)·z₀(x) + z₁(x) - t(x)c(x) = a(x)·[s₀(x)·c(x) + y₀(x)] + z₁(x) - [a(x)·s₀(x) + s₁(x)]c(x)

= a(x)·y₀(x) + z₁(x) - s₁(x)·c(x)

= a(x)y₀(x) + s₁(x)·c(x) + y₁(x) - s₁(x)·c(x)

= a(x)y₀(x) + y₁(x) = w(x) (as defined above)

This brief derivation demonstrates that the verification process will have c'(x) = c(x) if the signature was not tampered with.

Other Approaches

There are a number of other cryptographic signatures based on lattices over polynomial rings though not specifically in the Ring Learning With Errors construct explained by Lyubashevsky in his "Lattice Signatures without Trapdoors." Notable among these is the Learning with Errors Approach by Bai and Galbraith (which has a Ring-LWE variant) and the Trapdoor Lattice approach by Ducas, Durmas, Lepoint and Lyubashevsky .

Further Reading:

• The original Learning with Errors paper by Oded Regev. (updated version here)
• The original Learning with Errors Signature paper by Lyubashevsky. (here)
• The Gunesyu, Lyubashevsky, and Poppelmann RLWE-SIG paper. (here)