How to choose the distribution of error and secret vectors in LWE-based KEMs

Question

The general construction of a LWE-based PKE looks like the following:

KeyGen :

Secret vector, sk :$ s \leftarrow \chi_s^m$

Public Key, pk: ($A \leftarrow \mathbb{Z}_q^{m \times m}, t = As + e)$ where $e \leftarrow \chi_e^m$

Encryption : To encrypt a message $\mu \in \{0,1\}$, the encryptor chooses $r \in \chi_r^m$, $e_1\in \chi_{e_1}^m$ and $e_2 \in \chi_{e_2}$, and computes:

$u^T = r^TA + e_1^T$

$v = r^T t + e_2 + \lfloor \frac{q}{2} \rceil \mu$

Decryption : To decrypt, one computes $w = v-s^Tu$ and apply a rounding function, i.e., if $w$ is close to 0, output 0, else, if $w$ is close to $\lfloor \frac{q}{2} \rceil$ output 1.

---

Question 1

Is there any relation between the distributions $\chi_s, \chi_e, \chi_r, \chi_{e_1}, \chi_{e_2}$ that ensures IND-CPA security and structural security ? Which distributions are required to be same?

For example, we have listed the distributions used by existing KEMs.

Where,

1. CBD = Centerd Binomial Distribution;
2. $HWT_n(h)$ = Hamming Weight Ternary samples a ternary n-length vector of a fixed Hamming weight $h$
3. Rounding error: Error introduced through Learning with rounding (LWR)
4. $ZO_n(\rho)$ distribution samples a vector $v \in \{0,\pm 1\}^n$ with $Pr[v_i = 0] = 1 - \rho$, $Pr[v_i = -1] = Pr[v_i = 1] = \frac{\rho}{2}$

From the above table, we have the following observations:

1. $\chi_s = \chi_r$ except for Lizard where $ZO$ and $HWT$ are used (As per our knowledge, both are almost same except for their sampling techniques)
2. In Zhang et al. KEM, $\chi_s$ and $\chi_e$ are sampled from CBD but with distinct parameters i.e., Asymmetric MLWE (AMLWE) as an underlying hard problem.

Question 2

AMLWE is a case of MLWE where $\chi_s$ and $\chi_e$ are sampled from the same distribution but with different parameters. So, can we think of AMLWE as a particular case of LWE with $\chi_s \neq \chi_e$ ?

Answer 1

I'm not sure what you mean by "structural security". Generally, IND-CPA security is all you'd want (or more precisely, pseudorandomness of the (M/R)LWE distribution).

In general, this is a large research area, without many "succinct" answers. See for example this for a decent idea of what the state of the art of things is. At a high level though

1. results tend to depend rather strongly on the underlying problem. We have much stronger results available for LWE than RLWE or MLWE. In particular, it is known that it suffices for the error to be Gaussian, and secret to have sufficient min-entropy. It also can suffice for the secret to be binary.

2. some general results are still known, for example one may have the secret distribution be the same as the error distribution (source), rather than requiring the secrets be uniformly random. I think this extends to algebraically structured settings, and is why you see $\chi_e = \chi_s$ so much in the above.

That all being said, the above is for provable security results. Dually, one can wonder for which distributions do we have better attacks? Here, the conventional wisdom tends to be that the main parameter of the underlying distribution that matters is its standard deviation, at least for most "reasonable" distributions. In particular, attacks seem to behave similarly for things like

1. gaussian errors,
2. centered binomial errors,
3. uniform errors.

Certain assumptions (fixed hamming weight secrets) are perhaps more aggressive than others, and both small keys and small errors admit new attacks (though these attacks are not always the most performant, as they often strongly depend on a few of the many underlying parameters).

As for things like "rounding error", the story can get similarly confusing. Typically, our understanding of LWR with "small rounding" is not great. See for example this email thread, though it is a few years old at this point.