0
$\begingroup$

Assume that the same message is encrypted using two different keys within the BGV encryption scheme. Can we assume that the resulting ciphertext are indistinguishable?

I.e., given $c_1 = \text{Enc}(sk_1, m)$ and $c_2 = \text{Enc}(sk_2, m)$, are $c_1$ and $c_2$ indistinguishable?

If so, is there any proof of this in the literature?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Most schemes would be considered broken if this is not the case, for the simple reason that you would immediately leak information about the plaintext. Guess the plaintext, encrypt with your own key. By the way, we encrypt with the public key not the private key. And yes, this scheme is randomized using $r$ it seems. $\endgroup$
    – Maarten Bodewes ♦
    Nov 20 at 17:51
  • 2
    $\begingroup$ I don't understand that comment. That property is a form of anonymity, and it is not a standard property of encryption schemes. For example, RSA-based encryption schemes won't usually satisfy it: the distribution of ciphertexts easily reveals the top bits of the modulus (and even the exact modulus if the exponent is guaranteed to be small), so ciphertexts corresponding to different keys are definitely not indistinguishable, even though many RSA-based encryption schemes like RSA-OAEP or RSA-KEM are otherwise secure according to standard definitions. $\endgroup$
    – Mehdi Tibouchi
    Nov 22 at 10:15
  • 2
    $\begingroup$ In the case of LWE-based schemes, though, you can typically prove that property easily by applying the hardness of decisional LWE twice (to switch from one key to uniform to the other key). I haven't checked if it works out for BGV specifically but I expect it should. $\endgroup$
    – Mehdi Tibouchi
    Nov 22 at 10:18

0

Reset to default

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.