Ring learning with errors: Difference between revisions

Revision as of 21:47, 5 March 2015

Revision as of 17:43, 7 March 2015

Line 10:

== Trapdoor Free Lattice Signature (TFLS) ==

T

In this signature algorithm, we will be working in a ring (R) of polynomials of degree n with coefficients in the finite field Fq. We will follow the work of Gunesyu, Lyubashevsy, and Poppleman<ref name=":1" /> as well as that of Singh<ref name=":2" /> closely. Let q be prime and n be a power of 2.

Line 16 ⟶ 15:

=== Definitions: ===

Let

* R_n,q be the ring of polynomials with degree less than n and with coefficients in F_q with q a prime.

* a be a fixed publicly known polynomial in R_n,q

* b be an integer less than q which serves as a bound for polynomial coefficients over the integers

* s₁ be a randomly chosen secret polynomial in R_n,q

* s₂₁ be a randomly chosen secret polynomial in R_n.q with coefficients inchosen thebetween set (-1,0,1b) and (+b)

* s₁₂ be a randomly chosen secret polynomial in R_n,q with coefficients chosen between (-b) and (+b)

* the bounded polynomials s₁ and s₂ be the long term private signing key

* t = (a)(s₁)+s₂ be the long term public key for verification

* r₁ be a randomly chosen secret polynomial in R_n,q with coefficients chosen between (-b) and (+b)

* r₂ be a randomly chosen secret polynomial in R_n,q with coefficients inchosen thebetween set (-1,0,1b) and (+b)

* the bounded polynomials r₁ and r₂ be the short term (per signature) private signing key

* H(a,b) be a hash function which maps strings a and b to polynomials in Rn,qR with the property that all but 32j coefficients are 0 and the remaining coefficients are either 1 or -1.

Another parameter, an integer k, will be crucial to the security of the signatures scheme. Related to the definition of the hash function H(a,b), k will be chosen so that k-32j will define an "acceptance bound" for the polynomials created as the signature of the message. The coefficients of the signature polynomial will need to be between -(k-32j) and +(k+32j). If the coefficients of the computed polynomials are not in this range, the signature is "rejected" and the signing process starts over. This process is known as rejection sampling.

=== Signature Generation: ===

Line 38:

* Compute z₁ = (s₁)(c)+r₁

* Compute z₂ = (s₂)(c)+r₂

* If either z₁ or z₂ have coefficients outside the range -(k-32j) to +(k+32j) reject the signature and generate new values for r₁ and r₂

If z₁ and z₂ have coefficients in the correct range, accept the polynomials, c, z₁, and z₂ as the signature and transmit them, along with the message, to the verifier.