Ring learning with errors signature: Difference between revisions
Made the introduction and background more factual. Updated infromation |
Carvalho1988 (talk | contribs) Updated the example signature scheme to use more recent results. Removed any bias suggesting that the particular signature scheme was the only RLWE scheme worth considering. |
||
Line 13: | Line 13: | ||
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> 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|accessdate = 2015-05-24}}</ref> |
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> 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|accessdate = 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 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 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 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 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 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">{{Cite book|title=Cryptographic Hardware and Embedded Systems – CHES 2012|last=Güneysu|first=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 = in 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}}</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}}</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 ([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>{{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=https://eprint.iacr.org |
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}}</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}}</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 ([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://eprint.iacr.org|archive-date=26 August 2017|dead-url=|access-date=26 August 2017}}</ref> |
||
A RLWE-SIG works in the quotient [[ring of polynomials]] modulo a degree n polynomial Φ(x) with coefficients in the [[finite field]] Z<sub>q</sub> for an odd prime q ( i.e. the ring Z<sub>q</sub>[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: |
A RLWE-SIG works in the quotient [[ring of polynomials]] modulo a degree n polynomial Φ(x) with coefficients in the [[finite field]] Z<sub>q</sub> for an odd prime q ( i.e. the ring Z<sub>q</sub>[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 24: | Line 24: | ||
=== Generating "small" polynomials. === |
=== Generating "small" polynomials. === |
||
A RLWE |
A RLWE signature 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 when those coefficients are viewed as integers in Z rather than Z<sub>q</sub> .<ref name=":0" /> The signature algorithm will create random polynomials which are small with respect to a particular infinity norm bound. This is easily done by randomly generating all of the [[Coefficient|coefficients of the polynomial]] (a<sub>0</sub>, ..., a<sub>n-1</sub>) in a manner which is 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:<ref name=":1" /> |
||
* Using [[Uniform distribution (discrete)|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 [[Uniform distribution (discrete)|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. |
* 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 |
In the RLWE signature GLYPH used as an example below, coefficients for the "small" polynomials will use the [[Uniform distribution (discrete)|uniform sampling]] method and the value b will be much smaller than the value q.<ref name=":0" /> |
||
=== Hashing to a "small" polynomial === |
=== Hashing to a "small" polynomial === |
||
Most RLWE |
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 then an integer bound b (see above). |
||
=== Rejection sampling === |
=== Rejection sampling === |
||
A key feature of RLWE |
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 and "accepted" polynomial<ref name=":0" /> |
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 and "accepted" polynomial<ref name=":0" /> |
||
=== Other parameters === |
=== Other parameters === |
||
Following |
Following GLYPH 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<sub>q</sub> where q is an odd prime congruent to 1 mod 4. For n=1024, GLYPH sets q = 59393, b=16383 and k the number of non-zero coefficients in the output of Polyhash equal to 16.<ref name=":3" /> The number of non-zero coefficients k produced by the hash function 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" /><ref name=":3" /> |
||
As noted above, the polynomial Φ(x) which defines the ring of polynomials used will be x<sup>n</sup> + 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. |
As noted above, the polynomial Φ(x) which defines the ring of polynomials used will be x<sup>n</sup> + 1. Finally, a(x) will be a randomly chosen and fixed polynomial with coefficients from the set { -(q-1)/2 to (q-1)/2 }. The polynomial a(x) should be chosen in a "[[Nothing up my sleeve number|Nothing Up My Sleeve]]" manner such as [[One-way function|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. |
||
== Public key generation == |
== Public key generation == |
||
An entity wishing to sign messages generates its public key through the following steps: |
An entity wishing to sign messages generates its public key through the following steps: |
||
# Generate two small polynomials s |
# 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 |
# Compute t(x) = a(x)·s(x) + e(x) |
||
# Distribute t(x) as the entity's public key |
# Distribute t(x) as the entity's public key |
||
The polynomials s |
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<sub>1</sub>(x) and f<sub>2</sub>(x) such that: a(x)·f<sub>1</sub>(x) + f<sub>2</sub>(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] |
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 == |
== Signature generation == |
||
Following |
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<sub> |
# Generate two small polynomials y<sub>1</sub>(x) and y<sub>2</sub>(x) with coefficients from the set {-b, ..., 0, ...., b} |
||
# Compute w(x) = a(x)·y<sub> |
# Compute w(x) = a(x)·y<sub>1</sub>(x) + y<sub>2</sub>(x) |
||
# Map w(x) into a bit string ω |
# 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 c(x) = POLYHASH(ω | m) (This is a polynomial with k non-zero coefficients. The "|" denotes concatenation of strings) |
||
# Compute z<sub> |
# Compute z<sub>1</sub>(x) = s(x)·c(x) + y<sub>1</sub>(x) |
||
# Compute z<sub>1</sub>(x) = |
# Compute z<sub>1</sub>(x) = e(x)·c(x) + y<sub>2</sub>(x) |
||
# Until the infinity norms of z<sub> |
# Until the infinity norms of z<sub>1</sub>(x) and z<sub>2</sub>(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<sub> |
# The signature is the triple of polynomials c(x), z<sub>1</sub>(x) and z<sub>2</sub>(x) |
||
# Transmit the message along with c(x), z<sub> |
# Transmit the message along with c(x), z<sub>1</sub>(x) and z<sub>2</sub>(x) to the verifier. |
||
== Signature Verification == |
== Signature Verification == |
||
Following |
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<sub>0</sub>(x), z<sub>1</sub>(x)), and the message m. The verifier does the following: |
||
# Verify that the infinity norms of z<sub> |
# Verify that the infinity norms of z<sub>1</sub>(x) and z<sub>2</sub>(x) ≤ '''β''' , if not reject the signature. |
||
# Compute w'(x) = a(x)·z<sub> |
# Compute w'(x) = a(x)·z<sub>1</sub>(x) + z<sub>2</sub>(x) - t(x)c(x) |
||
# Map w'(x) into a bit string ω' |
# Map w'(x) into a bit string ω' |
||
# Compute c'(x) = |
# Compute c'(x) = POLYHASH(ω' | m) |
||
# If c'(x) ≠ c(x) reject the signature, otherwise accept the signature as valid. |
# If c'(x) ≠ c(x) reject the signature, otherwise accept the signature as valid. |
||
Notice that: |
Notice that: |
||
a(x)·z<sub> |
a(x)·z<sub>1</sub>(x) + z<sub>2</sub>(x) - t(x)c(x) = a(x)·[s(x)·c(x) + y<sub>1</sub>(x)] + z<sub>2</sub>(x) - [a(x)·s(x) + e(x)]c(x) |
||
{{=}} a(x)·y<sub> |
{{=}} a(x)·y<sub>1</sub>(x) + z<sub>2</sub>(x) - e(x)·c(x) |
||
{{=}} a(x)y<sub> |
{{=}} a(x)y<sub>1</sub>(x) + e(x)·c(x) + y<sub>2</sub>(x) - e(x)·c(x) |
||
{{=}} a(x)y<sub> |
{{=}} a(x)y<sub>1</sub>(x) + y<sub>2</sub>(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. |
This brief derivation demonstrates that the verification process will have c'(x) = c(x) if the signature was not tampered with. |
||
== Further developments == |
== Further developments == |
||
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: |
|||
There are a number of variations and refinements to the GLP signature that been proposed. These include: |
|||
* 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 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> |
* 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> |
Revision as of 19:00, 27 August 2017
![]() | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
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, the primary public key signatures currently in use (RSA and Elliptic Curve Signatures) will become completely insecure if scientists are ever able to build a moderately sized quantum computer.[1] 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 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.[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 Zq for an odd prime q ( i.e. the ring Zq[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:
The field Zq 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 xn + 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.
A RLWE signature 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 when those coefficients are viewed as integers in Z rather than Zq .[10] The signature algorithm will create random polynomials which are small with respect to a particular infinity norm bound. This is easily done by randomly generating all of the coefficients of the polynomial (a0, ..., an-1) in a manner which is 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:[13]
- 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 signature GLYPH 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.[10]
Hashing to a "small" polynomial
Most RLWE signature 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, 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 then 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.[13][12] 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 and "accepted" polynomial[10]
Other parameters
Following GLYPH and as noted above, the maximum degree of the polynomials will be n-1 and therefore have n coefficients.[10] Typical values for n are 512, and 1024.[10] The coefficients of these polynomials will be from the field Fq where q is an odd prime congruent to 1 mod 4. For n=1024, GLYPH sets q = 59393, b=16383 and k the number of non-zero coefficients in the output of Polyhash equal to 16.[14] The number of non-zero coefficients k produced by the hash function is equal to 32 for both cases.[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.[13][10][14]
As noted above, the polynomial Φ(x) which defines the ring of polynomials used will be xn + 1. Finally, a(x) will be a randomly chosen and fixed polynomial with coefficients from the set { -(q-1)/2 to (q-1)/2 }. 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.
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 f1(x) and f2(x) such that: a(x)·f1(x) + f2(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]
Signature generation
Following GLYPH,[14] to sign a message m expressed as a bit string, the signing entity does the following:
- Generate two small polynomials y1(x) and y2(x) with coefficients from the set {-b, ..., 0, ...., b}
- Compute w(x) = a(x)·y1(x) + y2(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 z1(x) = s(x)·c(x) + y1(x)
- Compute z1(x) = e(x)·c(x) + y2(x)
- Until the infinity norms of z1(x) and z2(x) ≤ β = (B - k) go to step 1. (This is the rejection sampling step noted above)
- The signature is the triple of polynomials c(x), z1(x) and z2(x)
- Transmit the message along with c(x), z1(x) and z2(x) to the verifier.
Signature Verification
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), z0(x), z1(x)), and the message m. The verifier does the following:
- Verify that the infinity norms of z1(x) and z2(x) ≤ β , if not reject the signature.
- Compute w'(x) = a(x)·z1(x) + z2(x) - t(x)c(x)
- Map w'(x) into a bit string ω'
- Compute c'(x) = POLYHASH(ω' | m)
- If c'(x) ≠ c(x) reject the signature, otherwise accept the signature as valid.
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.
Further developments
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]
A listing of various parameter sets for Ring Learning with Errors Signatures is given at ringlwe.info (click here)[17]
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."[18] See BLISS signature scheme
References
- ^ a b c d Dahmen-Lhuissier, Sabine. "ETSI - Quantum-Safe Cryptography". ETSI. Retrieved 2015-07-05.
- ^ Shah, Agam. "Quantum computing breakthrough claim from IBM". Retrieved 2015-06-01.
- ^ Markoff, John (2015-03-04). "Researchers Report Milestone in Developing Quantum Computer". The New York Times. ISSN 0362-4331. Retrieved 2015-07-05.
- ^ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1996). "Efficient Networks for Quantum Factoring". Physical Review A. 54 (2): 1034–1063. doi:10.1103/PhysRevA.54.1034. ISSN 1050-2947.
- ^ Smolin, John A.; Smith, Graeme; Vargo, Alexander (July 11, 2013). "Oversimplifying quantum factoring". Nature. 499 (7457): 163–165. doi:10.1038/nature12290. ISSN 0028-0836. PMID 23846653.
- ^ a b "Introduction". pqcrypto.org. Retrieved 2015-07-05.
- ^ "The Learning with Errors Problem" (PDF). www.cims.nyu.edu. Retrieved 2015-05-24.
- ^ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "On ideal lattices and learning with errors over rings". In Proc. of EUROCRYPT, volume 6110 of LNCS. Springer: 1–23.
- ^ "What does GCHQ's "cautionary tale" mean for lattice cryptography?". www.cc.gatech.edu. Retrieved 2015-07-05.
- ^ a b c d e f g h i Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems". In Prouff, Emmanuel; Schaumont, Patrick (eds.). Cryptographic Hardware and Embedded Systems – CHES 2012. Lecture Notes in Computer Science. Vol. 7428. Springer Berlin Heidelberg. pp. 530–547. doi:10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1.
- ^ Micciancio, Daniele (1998). "The shortest vector in a lattice is hard to approximate to within some constant". in Proc. 39th Symposium on Foundations of Computer Science: 92–98.
- ^ a b Lyubashevsky, Vadim (2009-01-01). Matsui, Mitsuru (ed.). Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 598–616. ISBN 978-3-642-10365-0.
- ^ a b c d e Lyubashevsky, Vadim (2011). "Lattice Signatures Without Trapdoors".
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ a b c d e Chopra, Arjun (2017). "GLYPH: A New Instantiation of the GLP Digital Signature Scheme". International Association of Cryptographic Research eprint Archive. Archived from the original (PDF) on 26 August 2017. Retrieved 26 August 2017.
{{cite web}}
: Cite has empty unknown parameter:|dead-url=
(help) - ^ "Cryptology ePrint Archive: Report 2013/838". eprint.iacr.org. Retrieved 2016-01-17.
- ^ "Cryptology ePrint Archive: Report 2015/755". eprint.iacr.org. Retrieved 2016-01-17.
- ^ "Parameters for RLWE". Ring Learning with Errors. Retrieved 2016-02-28.
- ^ "Cryptology ePrint Archive: Report 2013/383". eprint.iacr.org. Retrieved 2016-01-17.