Ring learning with errors key exchange: Difference between revisions

Revision as of 05:18, 18 July 2016

Revision as of 11:35, 23 July 2016

Line 40:

# 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 v(x) = 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 be small because e_R(x) was chosen to be small and the coefficients of e_I(x)s_R(x) will be bounded in their growth and still relatively small.''

# TheDepending distributionon ofthe specific scheme used, the coefficients of '''v(x)''' aremay smoothedbe byadded loopingwith throughsmall therandomized coefficientsvalues andto randomlyhide adjustingskewed certain valuesdistribution. For j = 0 to n-1:

# As '''v(x)''' and '''w(x)''' differ by small amount, a reconciliation information c is produced based on '''v(x)'''

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

# Respondent side's key stream u is calculated, based on the reconciliation information c and the polynomial '''v(x)'''.

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

# Two n-long bit streams, cj, and uj, are formed from the coefficients of v(x), (v_n-1, ... , v₀ ), via "Cross Rounding" and "Modular Rounding" respectively. For j = 0 to n-1:

## Set c_j to be the lowest bit of the [[Floor and ceiling functions|floor]] of quotient (4v_j)/q[[nearest integer function|;]] that is <math display="inline">c_j = \lfloor 4 v_j/q \rfloor\mod 2</math>

## Set u_j to be the lowest bit of the quotient (2v_j)/q after [[Nearest integer function|rounding]]; that is <math>u_j = \lfloor 2v_j/q\rceil\mod 2</math>

#Form the key (k) as the concatenation of u_n-1, ..., u₀.

# Form an n-long "reconciliation" bit string (c) as the concatenation of c_n-1, ..., c₀.

# Compute t_R(x) = a(x)·s_R(x) + e_R(x).

# The Respondent sends t_R(x) and c to the Initiator.

'''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 does not equal v(x) (above) the 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 stepsmethod will correct (with high probability) the differences.''

# 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

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

# Form the key (k) as the concatenation of u_n-1, ..., u₀

If the key exchange worked properly, the initiator's string: u_n-1, ..., u₀ and the respondent's string: u_n-1, ..., u₀ will be the same.

# Initiator side's key stream is produced from the reconciliation information c and polynomial '''w(x)'''.

Depending on the specifics of the parameters chosen n, q, σ, or b, there is an extremely small probability that this key exchange will fail to produce the same key. Parameters for the key exchange can be chosen to make the probability of failure in the key exchange very small; much less than the probability of undetectable garbles or device failures.

The methods of reconciliation and key string generation depends on the specific RLWE-KEX scheme in question. some method is based on modular arithmetic, while others may be based on high-dimension geometry. <ref name=":2"/><ref name=":3"/><ref name=":8"/>

If the key exchange worked properly, the initiator's string: u_n-1, ..., u₀ and the respondent's string: u_n-1, ..., u₀ will be the same.

Depending on the specifics of the parameters chosen n, q, σ, or b, there is an extremely small probability that this key exchange will fail to produce the same key. Parameters for the key exchange can be chosen to make the probability of failure in the key exchange very small; much less than the probability of undetectable garbles or device failures.

== Parameter Choices ==