Content deleted Content added
rewrote the lead to be similar to other wikipedia lead sections |
Link suggestions feature: 3 links added. |
||
| (79 intermediate revisions by 37 users not shown) | |||
Line 1:
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/|
Even though we do not know when a quantum computer to break RSA and other digital signature algorithms will exist, there
▲The Ring-LWE digital signature works in the ring of polynomials modulo a degree n polynomial Φ(x) with coefficients in the ring F<sub>q</sub> for an integer q ( i.e. the ring F<sub>q</sub>[x]/Φ(x) ). 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<sub>q</sub> 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<sup>n</sup> + 1. Other choices of n are possible but the corresponding cyclotomic polynomials are more complicated or their security not as well studied.
The signature algorithm uses polynomials which are considered "small" with respect to a measure called the "infinity norm." The infinity norm for a polynomial is simply the value of the largest coefficient of the polynomial when the representation of the ring elements are taken as the set { -(q-1)/2, ...-1, 0, 1, ... (q-1)/2 }. The algorithm will generate random polynomials which are small with respect to the infinity norm. This is done by randomly generating the coefficients of the polynomial (a<sub>n-1</sub>, ..., a<sub>0</sub>) which are guaranteed or very likely to be small. There are two common ways to do this:▼
# 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 coefficients from the set: { -β, -β+1, -β+2. ... -2, -1, 0, 1, 2, ... , β-2, β-1, β} the polynomial will be small with respect to the bound (β).▼
# Using Discrete Gaussian Sampling - For an odd value for 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 describe in full detail how this can be accomplished. A paper by Peikert, "An Efficient and Parallel Gaussian Sampler for Lattices provides a method for this sampling.<ref>{{Cite web|title = http://www.cc.gatech.edu/~cpeikert/pubs/pargauss.pdf|url = http://www.cc.gatech.edu/~cpeikert/pubs/pargauss.pdf|website = www.cc.gatech.edu|accessdate = 2015-05-30}}</ref> ▼
=== Generating "small" polynomials. ===
▲
▲
▲
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 ===
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 than an integer bound b (see above).
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 an "accepted" polynomial<ref name=":0" />
▲=== Rejection Sampling ===
▲An important feature of the Ring-LWE Signature algorithm is the use of a technique known as [[rejection sampling]]. In this technique if the infinity norm of the computed signature polynomials exceeds a fixed bound, '''β,''' the signature values will be discarded and the signing process will start again. This process will be repeated until the infinity norm of the signature polynomials 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.
===
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" />
An entity wishing to sign messages generates its public key through the following steps: ▼
# Generate two small polynomials s<sub>0</sub>(x) and s<sub>1</sub>(x) according to a distribution '''D'''. ▼
# Compute t(x) = a(x)·s<sub>0</sub>(x) + s<sub>1</sub>(x) ▼
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.
=== Signature Generation ===▼
To sign a message m expressed as a bit string, the signing entity does the following: ▼
# Compute w(x) = a(x)·y<sub>0</sub>(x) + y<sub>1</sub>(x) ▼
# Map w(x) into a bit string b ▼
# Compute c(x) = HASH(b | m) ▼
# Compute z<sub>0</sub>(x) = s<sub>0</sub>(x)·c(x) + y<sub>0</sub>(x) ▼
# Compute z<sub>1</sub>(x) = s<sub>1</sub>(x)·c(x) + y<sub>1</sub>(x) ▼
# Until the infinity norm of c(x) ≤ '''β''' then go to step 1. (This is the rejection sampling step noted above) ▼
# The signature is the triple of polynomials c(x), z<sub>0</sub>(x) and z<sub>1</sub>(x) ▼
# Transmit the message along with c(x), z<sub>0</sub>(x) and z<sub>1</sub>(x) to the verifier. ▼
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<sub>0</sub>(x), z<sub>1</sub>(x)), and the message m. The verifier does the following:▼
# Generate two small polynomials s(x) and e(x) with coefficients chosen uniformly from the set {-b,...-1, 0, 1, ..., b}
# Compute
#
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 c'(x) ≠ c(x) reject the signature.▼
Notice that a(x)·z<sub>0</sub>(x) + z<sub>1</sub>(x) - t(x)c(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]
= a(x)·[s<sub>0</sub>(x)·c(x) + y<sub>0</sub>(x)] + z<sub>1</sub>(x) - [a(x)·s<sub>0</sub>(x) + s<sub>1</sub>(x)]c(x) ▼
= a(x)·y<sub>0</sub>(x) + z<sub>1</sub>(x) - s<sub>1</sub>(x)·c(x)▼
▲
▲# Generate two small polynomials
# Compute c(x) = POLYHASH(ω | m) (This is a polynomial with k non-zero coefficients. The "|" denotes concatenation of strings)
▲# Until the infinity
== Signature Verification ==
▲
# Verify that the infinity norms of z<sub>1</sub>(x) and z<sub>2</sub>(x) ≤ '''β''' , if not reject the signature.
# Map w'(x) into a bit string ω'
▲# If c'(x) ≠ c(x) reject the signature, otherwise accept the signature as valid.
Notice that:
▲{{=}} a(x)
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 [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>
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]]
{{Reflist}}
==External links==
{{ Cryptography navbox | public-key }}
[[Category:Post-quantum cryptography]]
▲=== References ===
[[Category:Lattice-based cryptography]]
| |||