0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that the statement is in NP (the witness being the message and the encryption random coins). $\endgroup$ – fkraiem Jan 4 at 4:22
  • $\begingroup$ 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). $\endgroup$ – Mark Jan 6 at 3:08
1
$\begingroup$

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)$.

The bottom-line is: if you want such a zero-knowledge proof, you should specify which encryption scheme you want it for - for some classical schemes, no proof is needed.

$\endgroup$
0
$\begingroup$

For ElGamal, you can use the proof system proposed by Chaum & Pedersen (CRYPTO'92) "Wallet Databases with Observers."

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Viou Jan 4 at 11:13

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.

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