# Calculation of failure probability in basic Ring-LWE-DH key agreement

This is the basic unauthenticated Ring-LWE-based Diffie-Hellman key exchange, based on Peikert's Ring-LWE KEM: (from BCNS15)

• Alice and Bob have shared public polynomial $$a$$ randomly drawn from $$R_q = \mathbb{Z}_q[x]/(x^n+1)$$, and a known error distribution $$\chi$$ with standard deviation $$\sigma$$
• Alice generates random small secret polynomials $$s_A, e_A \in R_q$$ according to distribution $$\chi$$, calculates $$b_A = a \cdot s_A + e_A$$ and sends it to Bob
• Bob generates random small secret polynomials $$s_B, e_B \in R_q$$ according to distribution $$\chi$$, calculates $$b_B = a \cdot s_B + e_B$$ and sends it to Alice
• Alice calculates $$k_A = s_A \cdot b_B = a \cdot s_A \cdot s_B + s_A \cdot e_B$$
• Bob calculates $$k_B = s_B \cdot b_A = a \cdot s_A \cdot s_B + s_B \cdot e_A$$

$$k_A$$ and $$k_B$$ are approximately equal except for the error terms. So, Alice and Bob use a reconciliation function rec(.) such that rec($$k_A$$) = rec($$k_B$$) = $$K$$ is the common shared secret.

The basic reconciliation scheme (from BCNS15) rounds each coefficient of the polynomial to 0 or $$q/2$$, and $$q/2$$ is treated as 1, so that $$K$$ is an $$n$$-bit string. BCNS15 says that this scheme has a failure probability of $$1/2^{10}$$. How is this calculated?

Here is the general approach I have been trying:

• For successful key exchange, we must have $$|k_A[i] - k_B[i]| < \delta$$ for $$i \in \{0, 1, \cdots, n-1\}$$, where $$k_A[i]$$ and $$k_B[i]$$ denote the $$i$$-th coefficient of polynomials $$k_A$$ and $$k_B$$ respectively and $$\delta$$ is the error tolerance of the reconciliation scheme
• In this case, $$k_A - k_B = s_A \cdot e_B - s_B \cdot e_A$$ and $$\delta = q/4$$
• Let $$p$$ be the probability that $$|k_A[i] - k_B[i]| > \delta$$ for some $$i$$, that is, the probability of error in decoding any one bit of $$K$$. Then, the total failure probability is $$1 - (1 - p)^n \approx np$$ for small $$p$$
• Let the error distribution $$\chi$$ have a support $$[-t\sigma, +t\sigma]$$, where $$t$$ is a factor determined by the precision of the sampler implementation. Then, the maximum possible absolute value of any coefficient of $$s_A \cdot e_B$$ or $$s_B \cdot e_A$$ is $$nt^2\sigma^2$$, so we must have $$2nt^2\sigma^2 < q/4$$ or $$q > 8nt^2\sigma^2$$