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 '20 at 18:28
  • $\begingroup$ 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"... $\endgroup$ – Hilder Vitor Lima Pereira Oct 2 '20 at 18:41
  • $\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$ – 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.

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$ – absinthe_minded Oct 6 '20 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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