Ring learning with errors key exchange: Difference between revisions

Revision as of 19:56, 30 May 2015

Revision as of 18:31, 1 June 2015

Line 34:

'''Responder's Steps:'''

# Generate two small polynomials s_R(x) and e_R(x) by sampling from the distribution D.

# Compute '''v(x) =''' '''t_I(x)·s_R(x) + e_R(x)''' ''Note that thisv(x) equals:= a(x)s_I(x)s_R(x) + e_I(x)s_R(x) + e_R(x) and that e_R(x) + e_I(x)s_R(x) will also be small relativebecause e_R(x) was chosen to be small and the coefficients of e_I(x)s_R(x) will be no greater than the square of the coefficients of the small be small infinity norm on qbound.''

# The distribution of the coefficients of v(x) are smoothed by looping through the coefficients and randomly adjusting certain values. For j = 0 to n-1:

## If v_j = 0, draw a random bit (b). If b = 0 then v_j = 0 otherwise v_j = q-1

Line 49:

'''Initiators Final Steps:'''

# Receive t_R(x) and c from the Responder

# Compute '''w(x) = t_R(x)·s_I(x) + e_I(x)''' = a(x)s_I(x)s_R(x) + e_R(x)s_I(x) + e_I(x) ''Note that while this this does not equal v(x) (above) butthe first term in the result a(x)s_I(x)s_R(x) equals the first term in v(x) and the other terms are all small. The following reconciliation steps will correct (with high probability) isthe "closedifferences."''

# An n-long bit stream (uj) is formed by looping through the coefficients of w(x) and performing "Key Reconciliation." For j = 0 to n-1:

## If c_j = 0 and -q/8 ≤ w_j < 3q/8 then u_j = 0 otherwise u_j = 1

Line 65:

For 256 bits of security, n = 1024, q = 40961, and F(x) = x¹⁰²⁴ + 1

Because the key exchange uses random sampling and fixed bounds there is a small probability that the key exchange will fail to produce the same key for the initiator and responder. This is generally referred to as the soundness of the If we assume that the gaussian parameter σ is 8/sqrt(2π) and the uniform sampling bound (b) = 5 (see Singh)<ref name=":1" />, then the probability of key agreement failure is <u>less than</u> 2^-71 for the 128-bit secure parameters and 2^-91 for the 256-bit secure parameters.

=== Key Exchange Security ===