Ring learning with errors key exchange: Difference between revisions

Revision as of 01:44, 10 June 2015

Revision as of 11:56, 10 June 2015

Line 49:

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

## 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, ujcj, and cjuj, are formed from the coefficients of v(x), (v_n-1, ... , v₀ ), via "ModularCross Rounding" and "CrossModular Rounding" respectively. For j = 0 to n-1:

## FindSet mc_j andto be the lowest bit of the quotient r(4v_j)/q suchafter [[Floor and ceiling functions|rounding;]] that 2vis <sub>j</submath display="inline">c_j = m<sub>j<\lfloor 4 v_j/sub>q +\rceil\mod r<sub>j 2</submath>

## Set uj to be the lowest bit of the [[Floor and ceiling functions|floor]] of the quotient (2v_j)/q; that is <math>u_j = \lfloor 2v_j\rfloor\mod 2</math>

## Find s_j and y_j such that 4v_j = s_jq + y_j

##Form Ifthe r_j >key (q-1k)/2 (inas Z)the thenconcatenation setof u_jn-1, = m_j + 1 (mod 2) otherwise..., u_j0 = m_j (mod 2).

## If y_j > (q-1)/2 (in Z) then set c_j = s_j + 1 (mod 2) otherwise c_j = s_j (mod 2)

# 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).