Given a (El Gamal, for instance) ciphertext, can I (efficiently) prove that the ciphertext does not decrypt to plaintexts in a small set? For instance, given ciphertext $c = Enc(pk,2; r)$, can I (efficiently) prove that the ciphertext does not decrypt to a plaintext in set $S = \{0,1\}$?

I could use plaintext equality tests. For instance, I could construct ciphertexts $Enc(pk,0; 1)$ and $Enc(pk,1; 1)$, and use plaintext equality tests to show that neither of those ciphertexts is plaintext equivalent to ciphertext $c$. But, can I do better in terms of complexity?

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.