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

Question

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$

Answer 1

One concrete solution is to explicitly compute the distribution of each coefficients. In this particular ring, and if the distribution of the coefficients of e and s are symmetric, this ca just be computed as an 2n-fold convolution of the distribution of products of coefficients. An example (with some complication due to rounding) is available here:

https://github.com/pq-crystals/security-estimates/blob/master/Kyber_failure.py

More mathematical approaches (which may give somewhat looser bound) involve studying moment-generating function. This can be nicely abstracted away using the theory of sub-gaussian random variables.