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?


[1] Regev, Oded. "On lattices, learning with errors, random linear codes, and cryptography." Journal of the ACM (JACM) 56.6 (2009): 1-40.

  • 1
    $\begingroup$ What's a simple voting scheme? Could you clarify? $\endgroup$
    – Myath
    Oct 2, 2020 at 18:28
  • $\begingroup$ 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. $\endgroup$ Oct 2, 2020 at 21:07

1 Answer 1


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 "not trying to break LWE", 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] [...]

  • $\begingroup$ OK, I now see the issue. In what I was reviewing the vectors of a were constant and did not change in case of repetition so it created a big issue with a replay attack. Thanks a lot! $\endgroup$ Oct 6, 2020 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.