# 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. "On lattices, learning with errors, random linear codes, and cryptography." Journal of the ACM (JACM) 56.6 (2009): 1-40.

• What's a simple voting scheme? Could you clarify? – Myath Oct 2 '20 at 18:28
• Anyway, I think you are losing something, since a algorithm that breaks this scheme can be used to solve the LWE problem and it is really unlike that all the researchers that are trying to solve the LWE problem have missed this "simple voting scheme"... – Hilder Vitor Lima Pereira Oct 2 '20 at 18:41
• I'm not trying to break LWE, however, I believe that there could be a problem with applications that might end up sending the same message again. Let us assume that you have a message m and you will have to submit it several times to Alice using her public key. The only change you will have in these messages are the error vectors. You can then take all the sent messages and count how many times you had 1 in the first bit and how many 0. Since the error vectors are small, we can keep the bit that was used most times and thus remove the error bits. – absinthe_minded Oct 2 '20 at 21:07

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.
[...] 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] [...]