0
$\begingroup$

I know it is possible to prove zero knowledge that a given ElGamal ciphertext $(c,d)$ encrypts a plaintext belonging to some set ($\{0,1\}$ is frequently used for electronic voting applications).

Next I was thinking if it is also possible to prove encryption of a specific plaintext (i.e. the verifier knows the exact plaintext). A use case could be that someone sends a plaintext to some trusted service and obtains a ciphertext, along with a proof that the ciphertext really encrypts the plaintext. (The difference to the user encrypting the plaintext himself would be that the user does not learn the random parameter $r$ used in the encryption).

The basic approach that works fine for disjunctive proofs about set membership of the plaintext is: given $(c,d)=(g^r, mY^r)$ be the ElGamal ciphertext, where $r$ is drawn randomly and $Y=g^x$ is the public key.

  1. The prover decides on a random $s$
  2. The prover shares $(a,b)=(g^s, Y^s)$ with the verifier
  3. The verifier sends a random challenge $C$ to the prover
  4. The prover sends $z=s+Cr$ to the verifier
  5. The verifier verifies that $g^z=g^sg^{Cr}=ac^C$ and $Y^z=Y^sY^{Cr}=b\left(\frac{d}{m}\right)^C$

But as poncho pointed out, $m$ can directly be recovered from the equation of $Y^z$

Is there a similar proof that DOES prove proper encryption of a given plaintext?

Improve this question
$\endgroup$
5
  • $\begingroup$ For each specific plaintext, we have a proof of equality of two secrets ($r$), exactly the way you gave it. One would connect them with an OR-proof for different plaintexts. Informally, you prove one OR-option and simulate everything else. Even less formally, pick a proof system having individual challenges adding to the verifier' challenge. $\endgroup$
    – Vadym Fedyukovych
    Apr 9, 2021 at 12:03
  • $\begingroup$ Actually, the issue isn't just for low entropy plaintexts; if someone overhears the proof (and the public key and encryption), they can directly recover $m$ $\endgroup$
    – poncho
    Apr 9, 2021 at 13:12
  • $\begingroup$ @poncho oh, you are right. Obviously still lacking the sight to quickly spot things that should be obvious, such as m being a base and not an exponent. Editing the question to reflect this $\endgroup$
    – Andy
    Apr 9, 2021 at 15:24
  • $\begingroup$ With OR-proof, nobody knows which plaintext was simulated (phony), and which one was actually proved (is true). $\endgroup$
    – Vadym Fedyukovych
    Apr 9, 2021 at 19:36
  • $\begingroup$ Interesting idea.. maybe the prover can first prove e.g. that $m \in \{0,1\}$ and then that $m \in \{1,2\}$ using different nonces and ensuring the challenges are unrelated. Then the verifier will know that the plaintext was in fact 1 (if both proofs verify, of course). $\endgroup$
    – Andy
    Apr 10, 2021 at 8:49

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.