# zero knowledge proof of encryption

I am trying to see if there is a way to prove that a ciphertext c was encrypted under a given Public Key, Pk, without revealing the plain text message m.

• Note that the statement is in NP (the witness being the message and the encryption random coins). – fkraiem Jan 4 '19 at 4:22
• Do you want a proof of knowledge, or a proof of membership? Essentially, if you define $M_{c,Pk} = \{m\in \{0,1\}^*\mid \mathsf{Enc}_{Pk}(m) = c\}$, you could either prove that $M_{c,Pk}$ is non-empty (so there is some message $m$ that encrypts to $c$ under $Pk$), or you could prove that some specific message $m$ is in it (so there's some explicitly known message that encrypts to $c$ under $Pk$, for some choice of random coins). These are distinct as the randomness used isn't fixed (which Geoffroy's answer discusses). – Mark Jan 6 '19 at 3:08

For most classical encryption schemes from the literature, what you want will in fact be trivial, as it is common that every possible ciphertext is a valid encryption of at least some message $$m$$ with respect to the public key. This is not implied by the standard security properties (and does not hold, for example, with respect to IND-CCA secure encryption schemes), but it holds for many IND-CPA secure encryption schemes.
Take for example ElGamal over a group $$\mathbb{G}$$, with public key $$(g,h)$$ ans secret key $$s$$ such that $$h = g^s$$. Then any pair $$(c_1,c_2)$$ correspond to a valid encryption of some message $$m$$: set $$r$$ to be the value such that $$c_1 = g^r$$ (it exists since $$g$$ is a generator of $$\mathbb{G}$$), and set $$m$$ to be $$c_2/h^r$$. Then, you obviously have $$(c_1,c_2) = (g^r, h^rm)$$.
• How? this proof show the equality of two discrete logarithms. If your idea is to prove the correctess of the part ${\sf pk}^r \cdot m$ of the ciphertext using this proof, you need to reveal the message $m$. – Viou Jan 4 '19 at 11:13