Public key cryptography provides a rich set of different cryptographic algorithms the create digital signatures.
[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.
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.
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 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.
[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.
A RLWE signature uses polynomials which are considered "small" with respect to a measure called the "infinity norm".
[10] The signature algorithm will create random polynomials which are small with respect to a particular infinity norm bound.
[10] Most RLWE signature algorithms also require the ability to cryptographically hash arbitrary bit strings into small polynomials according to some distribution.
Rejection sampling ensures that the output signature is not exploitably correlated with the signer's secret key values.
[10] 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 a(x) should be chosen in a "Nothing Up My Sleeve" manner such as one-way hashing the output of a true noise random number generator (TRNG) or using the digital expansion of well known mathematical constans such as pi or e. All signers and verifiers of signatures will know n, q, b, k, Φ(x), a(x) and β = b-k. An entity wishing to sign messages generates its public key through the following steps: The polynomials s(x) and e(x) serve as the private key and t(x) is the corresponding public key.
[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: 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), z1(x), z2(x)), and the message m. The verifier does the following: Notice that: a(x)·z1(x) + z2(x) - t(x)c(x) = a(x)·[s(x)·c(x) + y1(x)] + z2(x) - [a(x)·s(x) + e(x)]c(x) = a(x)·y1(x) + z2(x) - e(x)·c(x) = a(x)y1(x) + e(x)·c(x) + y2(x) - e(x)·c(x) = a(x)y1(x) + y2(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.
It was developed by Ducas, Durmas, Lepoint and Lyubashevsky and documented in their paper "Lattice Signatures and Bimodal Gaussians.