Replay attacks and LWE Just a small question. Since in LWE the error is rather small, is there a problem with replay attacks? What I mean is that if we use the typical scheme of Regev [1] to encrypt a vector m, but this vector is sent, e.g. 1000 times, then an eavesdropper may perform a simple voting scheme to approximate the original message. Am I losing something?
References:
[1] Regev, Oded. &quot;On lattices, learning with errors, random linear codes, and cryptography.&quot; Journal of the ACM (JACM) 56.6 (2009): 1-40.
By looking the encryption procedure, you will see that we use a different sum of the vectors $\vec a_i$'s at each encryption. Thus, every ciphertext has the form
$$(\vec a, ~\vec a\cdot \vec s + e + \frac{p}{2} \cdot m)$$
with different terms $\vec a \in \mathbb{Z}_p^n$ and $e \in \mathbb{Z}$.
Notice that the probability that two ciphertexts have the same term $\vec a$ is already around $1/p^n$ (exponentially small), and the chance that you will see ciphertexts with the same pair $(\vec a, e)$ is even smaller.
Therefore, your attack does not work.
About the relation with LWE
You said that you are &quot;not trying to break LWE&quot;, but this scheme is CPA-secure under the assumption that the LWE problem is hard. Thus, even if you are not trying to solve the LWE problem directly, your attack would provides us with an algorithm for the LWE problem (because your attack satisfies the CPA-security game, since you are only using an encryption oracle). This is basically what Lemma 5.4 of this paper is saying:

[...] if there exists a polynomial time algorithm $W$ that distinguishes between encryptions of 0 and 1 then there exists a distinguisher $Z$ that distinguishes between $A_{\vec s,\chi}$ [the LWE distribution] and $U$ [the uniform distribution] [...]