Why is Ring-LWE based homomorphic encryption secure with one sample? Suppose $R=\mathbb{Z}[X]/f(X)$ is a polynomial ring.

Decisional Ring-LWE is hard if one cannot distinguish the following samples:


$(a_i, b_i) \in R^2$ for $i\in [0,k-1]$ (completely random)
$(a_i, b_i=a_is+e_i) \in R^2$ for $i\in [0,k-1]$ ($b_i$ is obtained by multiplication of $a_i$ and secret $s$ masked by some noise)


This requires $k$ samples.
However in homomorphic encryption scheme, key generation of public key requires just one Ring-LWE sample.

Why is this secure?
The security proofs on the papers about (R)LWE use several samples (usually denoted by $m$) because then the results (and the security guarantees) are stronger. And, anyway, they usually give upper bounds to $m$ (as being at most polynomially big in $n$), but not lower bounds.

For both, the decisional and the search version of the problem, giving less samples can only make the problem harder.

To see that, notice that if an attacker can distinguish the two distributions given only one sample, than it can break (R)LWE with multiple samples by just ignoring $m-1$ samples and distinguishing in the way he/she knows with one sample. And this argument works for any number of samples smaller than $m$ (so, we have a reduction from the (R)LWE problem with $m$ samples to the (R)LWE problem with any $m' &lt; m$ samples).

To be more confident about that, take a look at section 4.1.1 of A Decade of Lattice Cryptography, where Chris Peikert explains why we can ignore columns of the SIS problem. It is basically the same argument to your case.