Ring learning with errors signature: Difference between revisions

Revision as of 16:55, 5 July 2015

Revision as of 06:26, 6 July 2015

Line 1:

{{Multiple issues|

{{essay-like|date=July 2015}}

{{technical|date=July 2015}}

}}

[[Digital signature|Digital Signatures]] 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, all of the public key signatures currently in use 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><ref name=":3">{{Cite journal|title = Shor's Algorithm|url = https://en.wikipedia.org/wiki/Shor%2527s_algorithm|language = en}}</ref> New digital signature algorithms such as the Ring [[learning with errors]] signature ('''RLWE-SIG''') described in this article are examples of a new class of [[Quantum Safe Cryptography|Quantum Safe]] cryptographic algorithms designed to resist cryptanalytic attacks run on a [[Quantum computing|quantum computer]].<ref>{{Cite journal|title = Post-quantum key exchange for the TLS protocol from the ring learning with errors problem|url = http://eprint.iacr.org/2014/599|date = 2014|first = Joppe W.|last = Bos|first2 = Craig|last2 = Costello|first3 = Michael|last3 = Naehrig|first4 = Douglas|last4 = Stebila}}</ref><ref name=":1" />

[[Digital signature|Digital Signatures]] 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, all of the public key signatures currently in use 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><ref name=":3">{{Cite journal|title = Shor's Algorithm|url = https://en.wikipedia.org/wiki/Shor%2527s_algorithm|language = en}}</ref> New digital signature algorithms such as the Ring [[learning with errors]] signature ('''RLWE-SIG''') described in this article are examples of a new class of [[Quantum Safe Cryptography|Quantum Safe]] cryptographic algorithms designed to resist cryptanalytic attacks run on a [[Quantum computing|quantum computer]].<ref>{{Cite journal|title = Post-quantum key exchange for the TLS protocol from the ring learning with errors problem|url = http://eprint.iacr.org/2014/599|date = 2014|first = Joppe W.|last = Bos|first2 = Craig|last2 = Costello|first3 = Michael|last3 = Naehrig|first4 = Douglas|last4 = Stebila}}</ref><ref name=":1" />

== 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/|accessdate = 2015-06-01|first = Agam|last = Shah}}</ref><ref>{{Cite news|title = Researchers Report Milestone in Developing Quantum Computer|url = http://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 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 name=":3" /><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-10631034–1063|volume = 54|issue = 2|doi = 10.1103/PhysRevA.54.1034|first = David|last = Beckman|first2 = Amalavoyal N.|last2 = Chari|first3 = Srikrishna|last3 = Devabhaktuni|first4 = John|last4 = Preskill}}</ref><ref name=":3" /><ref name=":2" />

One of the most widely used public key algorithm used to create [[digital signatures]] is known as [[RSA]].<ref>{{Cite journal|title = RSA Cryptosystem|url = https://en.wikipedia.org/wiki/RSA_%2528cryptosystem%2529|language = en}}</ref>   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.<ref>{{Cite journal|title = Integer factorization records|url = https://en.wikipedia.org/w/index.php?title=Integer_factorization_records&oldid=669003206|date = 2015|language = en}}</ref>   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-165163–165|volume = 499|issue = 7457|doi = 10.1038/nature12290|language = en|first = John A.|last = Smolin|first2 = Graeme|last2 = Smith|first3 = Alexander|last3 = Vargo}}</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.<ref name=":3" /> 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.<ref name=":3" />

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|accessdate = 2015-07-05}}</ref><ref>{{Cite journal|title = Post-quantum cryptography|url = https://en.wikipedia.org/w/index.php?title=Post-quantum_cryptography&oldid=668208432|date = 2015|language = en}}</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|Learning with Errors]] problem.   The use of this problem in cryptography was introduced by Oded Regev in 2005 and has been the source of several cryptographic designs.<ref>{{Cite web|title = http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf|url = http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf|website = www.cims.nyu.edu|accessdate = 2015-05-24}}</ref>

The creators of the 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 journal|title = On ideal lattices and learning with errors over rings|url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.297.6108|publisher = Springer|journal = In Proc. of EUROCRYPT, volume 6110 of LNCS|date = 2010|pages = 1–23|first = Vadim|last = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev}}</ref><ref>{{Cite web|title = What does GCHQ's “cautionary"cautionary tale”tale" mean for lattice cryptography?|url = http://www.cc.gatech.edu/~cpeikert/soliloquy.html|website = www.cc.gatech.edu|accessdate = 2015-07-05}}</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" /> 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 = in Proc. 39th Symposium on Foundations of Computer Science|date = 1998|pages = 92–98|first = Daniele|last = Micciancio}}</ref>

The first RLWE-SIG was developed by Lyubashevsky in his paper "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}}</ref> 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 ([http://www.di.ens.fr/~lyubash/papers/signaturechess.pdf GLP]).<ref name=":0" />   A later section of this article provides references to other signatures based on Lyubashevsky's original work.

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

Line 18 ⟶ 21:

<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 F_q has its representative elements in the set { -(q-1)/2, ...-1, 0, 1, ... (q-1)/2 }. The polynomial Φ(x) will be xⁿ + 1.

=== Generating "Small" Polynomials. ===

Line 27 ⟶ 30:

=== Hashing to a "Small" Polynomial ===

Most RLWE-SIG 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, 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 [http://www.di.ens.fr/~lyubash/papers/signaturechess.pdf GLP] paper provides details on one way this can be easily done.<ref name=":0">{{Cite book|url = http://link.springer.com/chapter/10.1007/978-3-642-33027-8_31|publisher = Springer Berlin Heidelberg|date = 2012|isbn = 978-3-642-33026-1|pages = 530–547|series = Lecture Notes in Computer Science|language = en|first = Tim|last = Güneysu|first2 = Vadim|last2 = Lyubashevsky|first3 = Thomas|last3 = Pöppelmann|editor-first = Emmanuel|editor-last = Prouff|editor-first2 = Patrick|editor-last2 = Schaumont|doi = 10.1007/978-3-642-33027-8_31|chapter = Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|title = Cryptographic Hardware and Embedded Systems – CHES 2012|volume = 7428}}</ref>

=== Rejection Sampling ===

An key feature of RLWE-SIG algorithms is the use of a technique known as [[rejection sampling]].<ref name=":1" /> 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.

Line 36 ⟶ 40:

Following GLP and as noted above, the maximum degree of the polynomials will be n-1 and therefore have n coefficients.<ref name=":0" /> Typical values for n are 512, and 1024.<ref name=":0" /> 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¹⁵.<ref name=":0" /> The number of non-zero coefficients produced by the hash function (k) is equal to 32 for both cases.<ref name=":0" /> 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.<ref name=":1" /><ref name=":0" />

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 ==

Line 48 ⟶ 52:

== Signature Generation ==

Following GLP,<ref name=":0" />, 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)

Line 57 ⟶ 61:

# Until the infinity norms of z₀(x) and z₁(x) ≤ '''β''' 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 GLP,<ref name=":0" />, 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:

# 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 66 ⟶ 70:

# Compute c'(x) = HASH(ω' | m)

# 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)

Line 79 ⟶ 83:

== 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".<ref name=":1" /> Among these are the [https://eprint.iacr.org/2013/838.pdf 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 .<ref>{{Cite journal|title = An improved compression technique for signatures based on learning with errors|url = http://eprint.iacr.org/2013/838|date = 2013|first = Shi|last = Bai|first2 = Steven D.|last2 = Galbraith}}</ref><ref>{{Cite journal|title = Lattice Signatures and Bimodal Gaussians|url = http://eprint.iacr.org/2013/383|date = 2013|first = Léo|last = Ducas|first2 = Alain|last2 = Durmus|first3 = Tancrède|last3 = Lepoint|first4 = Vadim|last4 = Lyubashevsky}}</ref>.

== Further Readingreading ==

* The original Learning with Errors paper by Oded Regev.<ref>{{Cite journal|title = On Lattices, Learning with Errors, Random Linear Codes, and Cryptography|url = http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.5202|publisher = ACM Press|journal = In STOC|date = 2005|pages = 84–93|first = Oded|last = Regev}}</ref> (updated version [http://www.cims.nyu.edu/~regev/papers/qcrypto.pdf here])

* The original Learning with Errors Signature paper by Lyubashevsky.<ref name=":1" /> ([http://www.di.ens.fr/~lyubash/papers/LatticeSignature.pdf here])

* The Gunesyu, Lyubashevsky, and Poppelmann RLWE-SIG paper.<ref name=":0" /> ([http://www.di.ens.fr/~lyubash/papers/signaturechess.pdf here])

== References ==

{{Reflist}}

<nowiki/><nowiki/>