Score:0

Zero Knowledge proof of correct ElGamal encryption

do flag

Suppose for $sk = x$, $pk = g^x$ we encrypt message $m$ with ElGamal encryption as $(g^r,m\cdot pk^r)$. My goal is to prove that I performed the encryption correctly, i.e. that the same $r$ is used across $g^r$ and $m\cdot pk^r$.

I thought of a simple $\Sigma$-protocol to show this as follows:

  1. Prover samples $q_1,q_2$, computes $R_1 = q_1\cdot pk^{q_2}$ and $R_2 = g^{q_2}$ and sends $R_1, R_2$ to Verifier.
  2. Verifier sends random challenge $e$ to prover.
  3. Prover computes $z_1 = q_1 \cdot m^e$ and $z_2 = q_2 + e\cdot r$. Sends $z_1$ and $z_2$ to verifier.
  4. Verifier checks if $R_1 \cdot (m \cdot pk^r)^e= z_1 \cdot pk^{z_2}$ and $R_2 \cdot (g^r)^e = g^{z_2}$

By pen and paper the math checks out but I'm not sure if I miss something? (this question is a follow-up on an older related question of mine: Proof of correctness of an ElGamal encryption given a specific public key). For example, is there a chance that $z_1$ in practice could leak information about the message $m$?

Score:1
my flag

The proof doesn't work (even if you fix it up by having the prover initially send $R_1, R_2$, rather than $q_1, q_2$, which you likely intended); the holder of the private key can generate a valid looking proof, even if the ciphertext doesn't actually decrypt to the plaintext.

Suppose the prover has a public key $pk$ (and the corresponding private key); he has has a message $M'$ that bears no relation to the ciphertext $C$. Then, here is how he can generate a 'proof':

  • Steps 1, 2 proceeds as specified

  • In step 3, he computes $z_2 = q_2 + e \cdot r$ (as specified), however he computes $z_1 = R_1 \cdot C^e \cdot pk^{-z_2}$

  • In step 4, the verifier will note that both relations hold.

(That the verifier never uses the value of the supposed plaintext that the proof is supposed to be about should be enough to show that something is missing here...)

do flag
Thanks fixed the $R_1, R_2$. So my initial goal was to show that the prover used the same randomness $r$ for the two ElGamal ciphertexts. Would this proof prevent the prover from sending something like $(g^r, m \cdot pk^{r'}$ and $r \neq r'$?
Manish Adhikari avatar
us flag
@Panos Is $m$ supposed to be known to verifier. If not the statement is trivial: an $m$ always exist, and it actually is the proof of knowledge of $m$ by someone who does not hold the private key. In that case this looks OK, (I haven't seen the original version): an honest verifier simulator and extractor both exist. Otherwise, sigma protocol for DDH tuples are available, maybe you can use that.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.