2
$\begingroup$

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$
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.