Joint distribution of RLWE samples

Question

Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. We draw samples $s_i \gets R_q$ uniformly at random. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$. We compute the following quantities: $h_i = s_ip_1 + e_i$ where $p_1 \in R_q$ is a fixed polynomial. We note that $s_i$ and $e_i$ are not released. The common polynomial $p_1$ is chosen randomly and is shared for all $h_i$.

Based on the hardness of RLWE problem we know that $h_i$ is computationally indistinguishable from a random sample of $R_q$. I was wondering what guarantees we have on the joint distribution $(h_0, h_1, ...)$

Answer 1

It is not true that RLWE guarantees that $h_i$ is computationally indistinguishable from uniform for any fixed $p_1$: just consider the case of $p_1 = 0$.

At the opposite end, if $p_1$ is invertible is $R_q$ (which is the generic case), then each $h_i$ is exactly uniformly distributed in $R_q$, and they are all independent, so the joint distribution is just uniform on the product. You don't even need the randomness term for this to hold, so this is again unrelated to RLWE (remember that RLWE tells you something about the joint distribution $(s_i, h_i)$; since you're not including the $s_i$ part of the pair, it isn't really needed).

In the intermediate case when $p_1$ is a zero divisor but non zero, each $h_i$ is distributed as the sum of a uniform element of the ideal $p_1 R$ (which is entirely determined by the gcd between $p_1$ and $X^n+1$ over $\mathbb{F}_q$) and the randomness $\chi$. How hard it is to distinguish such samples from random will be basically determined by the codimension of the ideal as an $\mathbb{F}_q$-vector subspace of $R_q$ (i.e., the degree of the gcd) and the Gaussian width of $\chi$. In this case, again, you have independent samples from the same distribution, so there isn't much to say about the joint distribution of the $h_i$'s: it's just the product distribution.