Ring learning with errors signature: Difference between revisions

Revision as of 19:05, 27 August 2017

Latest revision as of 18:15, 3 July 2025

(32 intermediate revisions by 20 users not shown)

Line 1:

[[Digital signature]]s are a means to protect [[Digital data|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, the primary public key signatures currently in use ([[RSA (cryptosystem)|RSA]] and [[Elliptic Curve Digital Signature Algorithm|Elliptic Curve Signatures)]] will become completely insecure if scientists are ever able to build a moderately sized [[quantum computer]].<ref name=":2">{{Cite web|title = ETSI - Quantum-Safe Cryptography|url = http://www.etsi.org/technologies-clusters/technologies/quantum-safe-cryptography|website = ETSI|accessdateaccess-date = 2015-07-05|first = Sabine|last = Dahmen-Lhuissier}}</ref> [[Post-quantum cryptography|Post quantum cryptography]] is a class of cryptographic algorithms designed to be resistant to attack by a quantum cryptography. Several post quantum digital signature algorithms based on hard problems in lattices are being created replace the commonly used [[RSA (cryptosystem)|RSA]] and elliptic curve signatures. A subset of these lattice based scheme are based on a problem known as [[Ring learning with errors]]. Ring learning with errors based digital signatures are among the post quantum signatures with the smallest public key and signature sizes

{{Multiple issues|}}

[[Digital signature]]s are a means to protect [[Digital data|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, the primary public key signatures currently in use ([[RSA (cryptosystem)|RSA]] and [[Elliptic Curve Digital Signature Algorithm|Elliptic Curve Signatures)]] will become completely insecure if scientists are ever able to build a moderately sized [[quantum computer]].<ref name=":2">{{Cite web|title = ETSI - Quantum-Safe Cryptography|url = http://www.etsi.org/technologies-clusters/technologies/quantum-safe-cryptography|website = ETSI|accessdate = 2015-07-05|first = Sabine|last = Dahmen-Lhuissier}}</ref> [[Post-quantum cryptography|Post quantum cryptography]] is a class of cryptographic algorithms designed to be resistant to attack by a quantum cryptography. Several post quantum digital signature algorithms based on hard problems in lattices are being created replace the commonly used [[RSA (cryptosystem)|RSA]] and elliptic curve signatures. A subset of these lattice based scheme are based on a problem known as [[Ring learning with errors]]. Ring learning with errors based digital signatures are among the post quantum signatures with the smallest public key and signature sizes

== Background ==

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.<ref>{{Cite web|title = Quantum computing breakthrough claim from IBM|url = http://www.cio.co.uk/news/r-and-d/quantum-computing-breakthrough-claim-from-ibm-3609914/|accessdateaccess-date = 2015-06-01|first = Agam|last = Shah|archive-date = 2015-09-23|archive-url = https://web.archive.org/web/20150923203728/http://www.cio.co.uk/news/r-and-d/quantum-computing-breakthrough-claim-from-ibm-3609914/|url-status = dead}}</ref><ref>{{Cite news|title = Researchers Report Milestone in Developing Quantum Computer|url = https://www.nytimes.com/2015/03/05/science/quantum-computing-nature-google-uc-santa-barbara.html|newspaper = The New York Times|date = 2015-03-04|access-date = 2015-07-05|issn = 0362-4331|first = John|last = Markoff}}</ref> 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|public key]] cryptography algorithms used to protect privacy and digitally sign information on the internet.<ref name=":2" /><ref>{{Cite journal|title = Efficient Networks for Quantum Factoring|url = http://arxiv.org/abs/quant-ph/9602016|journal = Physical Review A|date = 1996|issn = 1050-2947|pages = 1034–1063|volume = 54|issue = 2|doi = 10.1103/PhysRevA.54.1034|firstpmid = 9913575|first1 = David|lastlast1 = Beckman|first2 = Amalavoyal N.|last2 = Chari|first3 = Srikrishna|last3 = Devabhaktuni|first4 = John|last4 = Preskill|arxiv = quant-ph/9602016|bibcode = 1996PhRvA..54.1034B|s2cid = 2231795}}</ref>

One of the most widely used public key algorithm used to create [[digital signatures]] is known as [[RSA (cryptosystem)|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|Shor’s algorithm]] will easily accomplish the task.<ref>{{Cite journal|title = Oversimplifying quantum factoring|url = http://www.nature.com/nature/journal/v499/n7457/full/nature12290.html|journal = Nature|date = July 11, 2013|issn = 0028-0836|pages = 163–165|volume = 499|issue = 7457|doi = 10.1038/nature12290|firstfirst1 = John A.|lastlast1 = Smolin|first2 = Graeme|last2 = Smith|first3 = Alexander|last3 = Vargo|pmid=23846653|arxiv = 1301.7007|bibcode = 2013Natur.499..163S|s2cid = 4422110}}</ref> 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 cryptography|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.<ref name=":2" /><ref name=":4">{{Cite web|title = Introduction|url = http://pqcrypto.org/|website = pqcrypto.org|accessdateaccess-date = 2015-07-05}}</ref> This new area of cryptography is called [[Post-quantum cryptography|Post Quantum]] or [[Quantum Safe Cryptography|Quantum Safe]] cryptography.<ref name=":2" /><ref name=":4" /> 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|Learning with Errors]] problem in cryptography was introduced by Oded Regev in 2005 and has been the source of several cryptographic designs.<ref>{{Cite web|title = The Learning with Errors Problem|url = http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf|website = www.cims.nyu.edu|accessdateaccess-date = 2015-05-24}}</ref>

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.<ref>{{Cite journalbook |titledate = On2010|pages ideal= lattices1–23|first1 and= learningVadim|last1 with= errorsLyubashevsky|first2 over= ringsChris|urllast2 = http://citeseerx.ist.psu.edu/viewdoc/summary?doiPeikert|first3 =10.1.1.297.6108 Oded|publisherlast3 = SpringerRegev|journal title=Advances Inin Proc.Cryptology of– EUROCRYPT, volume2010 6110 of LNCS|date chapter=On 2010|pagesIdeal =Lattices 1–23|firstand =Learning with Errors over Rings Vadim|last series=Lecture Notes in Computer Science Lyubashevsky|first2 volume=6110 Chris|last2citeseerx = Peikert10.1.1.297.6108|doi=10.1007/978-3-642-13190-5_1|first3 isbn=978-3-642-13189-9 Oded|last3 editor-last=Gilbert|editor-first=Henri Regev}}</ref><ref>{{Cite web|title = What does GCHQ's "cautionary tale" mean for lattice cryptography?|url = http://www.cc.gatech.edu/~cpeikert/soliloquy.html|website = www.cc.gatech.edu|accessdateaccess-date = 2015-07-05|url-status = dead|archive-url = https://web.archive.org/web/20150706150530/http://www.cc.gatech.edu/~cpeikert/soliloquy.html|archive-date = 2015-07-06}}</ref> The signature described below has a provable reduction to the [[Shortest vector problem|Shortest Vector Problem]] in an [[Ideal lattice cryptography|ideal lattice]].<ref name=":0">{{Cite book|title=Cryptographic Hardware and Embedded Systems – CHES 2012|lastlast1=Güneysu|firstfirst1=Tim|last2=Lyubashevsky|first2=Vadim|last3=Pöppelmann|first3=Thomas|date=2012|publisher=Springer Berlin Heidelberg|year=|isbn=978-3-642-33026-1|editor-last=Prouff|editor-first=Emmanuel|series=Lecture Notes in Computer Science|volume=7428|___location=|pages=530–547|chapter=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|doi=10.1007/978-3-642-33027-8_31|editor-last2=Schaumont|editor-first2=Patrick}}</ref> 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.<ref>{{Cite journal|title = The shortest vector in a lattice is hard to approximate to within some constant|url = http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.7305|journal = inIn Proc. 39th Symposium on Foundations of Computer Science|date = 1998|pages = 92–98|first = Daniele|last = Micciancio}}</ref>

The first RLWE based signature was developed by Lyubashevsky in his paper "Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures"<ref name=":5">{{Cite book|title = Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures|url = http://link.springer.com/chapter/10.1007/978-3-642-10366-7_35|publisher = Springer Berlin Heidelberg|date = 2009-01-01|isbn = 978-3-642-10365-0|pages = 598–616|series = Lecture Notes in Computer Science|first = Vadim|last = Lyubashevsky|editor-first = Mitsuru|editor-last = Matsui|doi = 10.1007/978-3-642-10366-7_35|title = Advances in Cryptology – ASIACRYPT 2009|volume = 5912|chapter = Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures}}</ref> and refined in "Lattice Signatures Without Trapdoors" in 2011.<ref name=":1">{{Cite journal|title = Lattice Signatures Without Trapdoors|url = http://eprint.iacr.org/2011/537|date = 2011|first = Vadim|last = Lyubashevsky| journal=Cryptology ePrint Archive }}</ref> 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 ([https://web.archive.org/web/20140518004537/http://www.di.ens.fr/~lyubash/papers/signaturechess.pdf GLP]).<ref name=":0" /> This presentation is based on a 2017 update to the GLP scheme called GLYPH.<ref name=":3">{{Cite web|url=https://eprint.iacr.org/2017/766.pdf|title=GLYPH: A New Instantiation of the GLP Digital Signature Scheme|last=Chopra|first=Arjun|date=2017|website=International Association of Cryptographic Research eprint Archive|archive-url=https://web.archive.org/web/20170828012937/https://eprint.iacr.org/2017/766.pdf|archive-date=2628 August 2017|dead-url=|access-date=26 August 2017|url-status=bot: unknown}}</ref>

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) ).<ref name=":1" /> 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:

<math>a(x) = a_0 + a_1x + a_{2}x^2 + \ldots + a_{n-3}x^{n-3} + a_{n-2}x^{n-2} + a_{n-1}x^{n-1}</math>

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.

=== Generating "small" polynomials. ===

Line 27 ⟶ 25:

=== Hashing to a "small" polynomial ===

Most RLWE signature algorithms also require the ability to [[Cryptographic hash function|cryptographically hash]] arbitrary bit strings into small polynomials according to some distribution. The example below uses a hash function, POLYHASH(ω), which accepts a bit string, ω, as input and outputs a polynomial with n coefficients such that exactly k of these coefficients have absolute value greater than zero and less thenthan an integer bound b (see above).

=== Rejection sampling ===

A key feature of RLWE signature algorithms is the use of a technique known as [[rejection sampling]].<ref name=":1" /><ref name=":5" /> 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 and k will be the number of non-zero coefficients allowed in andan "accepted" polynomial<ref name=":0" />

=== Other parameters ===

Line 40 ⟶ 38:

== Public key generation ==

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

# Generate two small polynomials s(x) and e(x) with coefficients chosen uniformly from the set {-b,...-1, 0, 1, ..., b}

# Compute t(x) = a(x)·s(x) + e(x)

# 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|Ideal Lattice Cryptography]] for more details on the theoretical difficulty of this problem]

== Signature generation ==

Following GLYPH,<ref name=":3" /> to sign a message m expressed as a bit string, the signing entity does the following:

# Generate two small polynomials y₁(x) and y₂(x) with coefficients from the set {-b, ..., 0, ...., b}

# Compute w(x) = a(x)·y₁(x) + y₂(x)

# Map w(x) into a bit string ω

# Compute c(x) = POLYHASH(ω | m) (This is a polynomial with k non-zero coefficients. The "|" denotes concatenation of strings)

# Compute z₁(x) = s(x)·c(x) + y₁(x)

# Compute z₁₂(x) = e(x)·c(x) + y₂(x)

# Until the infinity norms of z₁(x) and z₂(x) ≤ '''β = ('''B - k) go to step 1. (This is the rejection sampling step noted above)

# The signature is the triple of polynomials c(x), z₁(x) and z₂(x)

# Transmit the message along with c(x), z₁(x) and z₂(x) to the verifier.

== Signature Verification ==

Following GLYPH,<ref name=":3" /> 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:

# Verify that the infinity norms of z₁(x) and z₂(x) ≤ '''β''' , if not reject the signature.

# Compute w'(x) = a(x)·z₁(x) + z₂(x) - t(x)c(x)

Line 83 ⟶ 81:

* Work by Bai and Galbraith on short signatures documented [https://eprint.iacr.org/2013/838 here].<ref>{{Cite web|title = Cryptology ePrint Archive: Report 2013/838|url = https://eprint.iacr.org/2013/838|website = eprint.iacr.org|access-date = 2016-01-17}}</ref>

* Work by Akleylek, Bindel, Buchmann, Kramer and Marson on security proofs for the signature with fewer security assumptions and documented [https://eprint.iacr.org/2015/755 here].<ref>{{Cite web|title = Cryptology ePrint Archive: Report 2015/755|url = https://eprint.iacr.org/2015/755|website = eprint.iacr.org|access-date = 2016-01-17}}</ref>

A listing of various parameter sets for Ring Learning with Errors Signatures is given at ringlwe.info ([http://www.ringlwe.info/parameters-for-rlwe.html click here])<ref>{{Cite web

| url = http://www.ringlwe.info/parameters-for-rlwe.html

| title = Parameters for RLWE

| website = Ring Learning with Errors

| access-date = 2016-02-28

}}</ref>

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."<ref>{{Cite web|title = Cryptology ePrint Archive: Report 2013/383|url = https://eprint.iacr.org/2013/383|website = eprint.iacr.org|access-date = 2016-01-17}}</ref> See [[BLISS signature scheme]]

Line 94 ⟶ 86:

== References ==

{{Reflist}}

==External links==

{{ Cryptography navbox | public-key }}

[[Category:Post-quantum cryptography]]

[[Category:Lattice-based cryptography]]