High Hamming Weight Attack on Kyber

Question

I was reading LAC (https://eprint.iacr.org/2018/1009.pdf). They mention about high-hamming weight attacks on the Centered Binomial Distribution (CBD). To counter this, they propose CBD with fixed hamming weight.

To prevent high hamming weigh attacks, we switch to n-ary centered binomial distribution with fixed Hamming weight. This makes LAC com- pletely immune from high Hamming weight attacks and their potential variants.

KYBER uses CBD. Does these kinds of high-hamming weight attacks effects Kyber? In the security analysis of Kyber, I have not came across any such discussion? Are these attacks really serious?

---

Centered Binomial Distribution (CBD) is defined in Kyber as:

Sampling from a binomial distribution. Noise in Kyber is sampled from a centered binomial distribution $B_{\eta}$ for $\eta = 2$ or $\eta = 3$. We define $B_{\eta}$ as follows:

$$ \text{Sample} (a_1, \ldots, a_{\eta}, b_1, \ldots, b_{\eta}) \leftarrow \{0,1\}^{2\eta} \\ \text{and output} \sum_{i=1}^{\eta} (a_i - b_i). $$

When we write that a polynomial $f \in R_q$ or a vector of such polynomials is sampled from $B_{\eta}$, we mean that each coefficient is sampled from $B_{\eta}$.

For the specification of Kyber we need to define how a polynomial $f \in R_q$ is sampled according to $B_{\eta}$ deterministically from $64\eta$ bytes of output of a pseudorandom function (we fix $n = 256$ in this description). This is done by the function CBD (for "centered binomial distribution") defined as described in Algorithm 2.

Algorithm 2: $\text{CBD}_{q}: \mathbb{B}^{64\eta} \rightarrow R_q$

• Input: Byte array $B = (b_0, \ldots, b_{64\eta-1}) \in \mathbb{B}^{64\eta}$
• Output: Polynomial $f \in R_q$

$(\beta_0, \ldots, \beta_{512\eta-1}) = \text{BytesToBits}(B)$
for $i$ from 0 to 255 do
  $a = \sum_{j=0}^{\eta-1} \beta_{2\eta i+j}$
  $b = \sum_{j=0}^{\eta-1} \beta_{2\eta i+\eta+j}$
  $f_i = a - b$
end for
return $f_0 + f_1x + f_2x^2 + \ldots + f_{255}x^{255}$

Answer 1

*-LWE systems are all based around the idea of adding "noise" to a constrained linear system. Any non-zero noise will prevent the linear system being directly solvable using linear algebra and require less direct methods to recover the most likely constrained solution (e.g. exhaustion over possible noise values or techniques from lattice problems). By making the work required for these less direct methods large, we hope to develop a secure system.

There are a couple of ways that the added noise can be problematic.

1. If it's not "noisy" enough so that the some of the less direct methods become feasible e.g. if the "error" is all zeros apart from a single +1 entry it is easy to exhaust over all possible locations of the non-zero and solve using linear algebra.
2. If it's too "noisy" so that the most likely constrained solution is not the same as the solution that was used to generate the system. Cryptographically speaking this leads to decryption failures. The fact that such a failure has taken place provides information about the secret values used, which is a cryptographic no-no.

For various systems, the noise needs to be generated randomly and LAC decided to use a random generation method where all of the noise generated is always equally noisy (technically speaking so that all of the various norms of the error vectors are always the same). They do this by always using $n$-long error vectors with $h/2$ entries set to +1, $h/2$ entries set to -1 and the remaining $n-h$ entries set to 0. Mathematically speaking, I find it strange to describe this probability distribution as a CBD with fixed Hamming weight, but we'll let that slide. This means that from the point of view of our two issues, no particular LAC error vector is more likely to be problematic than any other.

Kyber on the other hand, sticks with the pragmatic and easier-to-implement CBD described in the question which admits varying amounts of "noisiness" so that both issues are theoretically possible but very highly unlikely.

For example in Algorithm 2 in the question with $\eta=2$, there is a $256(3/8)^{255}(1/4)\approx 2^{-355}$ chance of getting and output where 255 of the $f_i$ are zero and the other one is +1.

Statistics provides ways of estimating the probability of more general undesirable forms of noise e.g. Chernoff's bounds tell us that there is a less than $\exp(-64/3)\approx 2^{-31}$ chance of getting an output with 128 or more of the $f_i$ equal to $\pm 2$.

All therefore should be fine with very high probability when error vectors are generated according to the specification. However, it becomes necessary to consider unsporting line of cryptanalysis where adversaries attempt to use extreme error vectors in the hope of causing a decryption failure and this revealing secret information. To offset this designers put in mechanisms that try to ensure that the errors are legitimately generated. To do this, successful decapsulation must allow recovery of the encapsulator's error. In the case of LAC, a simple count of +1s, -1s and 0s distinguishes valid error vectors for invalid ones. In the case of Kyber, error vectors are deterministically constructed from as secret seed value which is recovered as part of the decapsulation process. The decapsulator is then supposed to re-run the encapsulator's error generation process and verify that the error was generated according to the specification. Note that if an illegitimate error vector is identified, it is vital that the implementation produces no response that allows this case to be differentiated from a decryption failure. Students of real-world cryptanalysis may have opinions on how easy this is to achieve in practice.

Another issue is that just because a Kyber error vector has been legitimately generated does not mean that it is not problematic. A determined adversary can exhaust through many secret seeds, looking for one which produces an especially troublesome error vector. This is known as failure boosting (link as per Mark in the question comments). Troublesome error vectors are supposed to be rare so the exhaust needs to be large and the parameters of Kyber mean the trade-off between induced failures and the work to find error vectors with higher failure rates is not an issue for typical Kyber encapsulator secrets (this is a qualitative interpretation of the curve corresponding to Kyber in figures 2 and 3 of the paper). The designers further block a bulk pre-computation of error seeds by making the encapsulator's public key a part of the seeding process.

One piece of analysis missing from the failure-boosting paper (which may have been covered by subsequent work), is the effect of the attack on a weak(er) subset of encapsulator keys. The paper's analysis covers the average failure rate for all Kyber encapsulator keys, but some encapsulator keys will be more problematic than others and failure boosting will be commensurably more effective on these. This would be particularly dangerous if the potential weakness can be efficiently tested for in even a statistical sense. Overall however, the error boosting analysis to date is not a cause for concern for Kyber.