Ring learning with errors signature

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.[2][3] A relatively small quantum computer capable of processing only ten thousand of bits of information would easily break all of the widely used public key cryptography algorithms used to protect privacy and digitally sign information on the internet.[1][4]

One of 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. 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 factor the product of two n-bit primes, a quantum computer with roughly 6n bits of logical qubit memory and capable of executing a program known as Shor's algorithm will easily accomplish the task.[5] 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 could quickly 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 and other digital signature algorithms will exist, there has been active research over the past decade to create cryptographic algorithms which remain secure even when an attacker has the resources of a quantum computer at their disposal.[1][6] This new area of cryptography is called Post Quantum or Quantum Safe cryptography.[1][6] This article is about one class of these algorithms: digital signatures based on the Ring Learning with Errors problem. The use of the general Learning with Errors problem in cryptography was introduced by Oded Regev in 2005 and has been the source of several cryptographic designs.[7]

The creators of the Ring-based Learning with Errors (RLWE) basis for cryptography believe that an important feature of these algorithms based on Ring-Learning with Errors is their provable reduction to known hard problems.[8][9] The signature described below has a provable reduction to the Shortest Vector Problem in an ideal lattice.[10] 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.[11]

The first RLWE based signature was developed by Lyubashevsky in his paper "Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures"[12] and refined in "Lattice Signatures Without Trapdoors" in 2011.[13] A number of refinements and variants have followed. This article highlights the fundamental mathematical structure of RLWE signatures and follows the original Lyubashevsky work and the work of Guneysu, Lyubashevsky and Popplemann (GLP).[10] This presentation is based on a 2017 update to the GLP scheme called GLYPH.[14]

A RLWE-SIG works in the quotient ring of polynomials modulo a degree n polynomial Φ(x) with coefficients in the finite field Z_q for an odd prime q ( i.e. the ring Z_q[x]/Φ(x) ).[13] 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:

${\displaystyle 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 Z_q has its representative elements in the set { -(q-1)/2, ...-1, 0, 1, ... (q-1)/2 }. When n is a power of 2, the polynomial Φ(x) will be the cyclotomic polynomial xⁿ + 1. Other choices of n are possible but the corresponding cyclotomic polynomials are more complicated or their security not as well studied.

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

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

The polynomials s(x) and e(x) serve as the private key and t(x) is the corresponding public 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 difficult to forge. [See the Wikipedia article on Ring Learning with Errors or Ideal Lattice Cryptography for more details on the theoretical difficulty of this problem]

Following GLYPH,[14] 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) = POLYHASH(ω | 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) = e(x)·c(x) + y₂(x)
7. Until the infinity norms of z₁(x) and z₂(x) ≤ β = (B - k) 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.

Following GLYPH,[14] to verify a message m expressed as a bit string, the verifying entity must possess 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) = POLYHASH(ω' | 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) + e(x)]c(x)

= a(x)·y₁(x) + z₂(x) - e(x)·c(x)

= a(x)y₁(x) + e(x)·c(x) + y₂(x) - e(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.

The GLYPH signature scheme described in this document closely follows the work of Lyubashevsky, Gunesyu and Popplemen from 2011 and 2012. There are a number of other variations to their work. These include:

• Work by Bai and Galbraith on short signatures documented here.[15]
• Work by Akleylek, Bindel, Buchmann, Kramer and Marson on security proofs for the signature with fewer security assumptions and documented here.[16]

Another approach to signatures based on lattices over Rings is a variant of the patented NTRU family of lattice based cryptography. The primary example of this approach is a signature known as the Bimodal Lattice Signature Scheme (BLISS). It was developed by Ducas, Durmas, Lepoint and Lyubashevsky and documented in their paper "Lattice Signatures and Bimodal Gaussians."[17] See BLISS signature scheme