If Alice encrypts two messages $a$ and $b$, such that $x=E(a)$, $y=E(b)$. Can Alice prove (without revealing $a$, $b$ or the private key) that $a = b$?

Obviously the proof must not be too long and it should be practical to compute and verify (either interactively or non-interactively).

This is possible for the Pohlig-Hellman symmetric cipher, even if the ciphertexts are encrypted with different keys. But P-H is not public key.

If such a cryptosystem exists (and it is commutative or provides public re-encryption), then one of the limitations in Mental Poker protocols could be solved. The problem is the existence (or not) of a protocol that can provide both semantic security and abrupt drop out tolerance (without any threshold scheme). Edit: It seems that the encryption needs to be deterministic to be able to support drop-out tolerance, and I see no way to overcome this. Without determinism, I was only able to veto the cards of a single player from a new deck.

See What is the theoretical and practical status of mental poker? for a related question.

  • $\begingroup$ Would it have to be zero knowledge, or would it be enough if semantic security was preserved? $\:$ $\endgroup$
    – user991
    Commented Oct 11, 2012 at 19:21
  • $\begingroup$ It does not need to be perfect zero knowledge. I suppose semantic security is enough. A computational zero knowledge argument will do fine. $\endgroup$
    – SDL
    Commented Oct 11, 2012 at 19:43
  • $\begingroup$ (Note than an argument system could preserve semantic security without $\hspace{1.9 in}$ even being computationally zero knowledge.) $\:$ $\endgroup$
    – user991
    Commented Oct 12, 2012 at 1:52

4 Answers 4


Yes. Such proofs are possible for El Gamal.

It involves a zero knowledge proof of equality of a discrete log, together with the homomorphic property of El Gamal encryption.

Recall that given $E(a)$ and $E(b)$, anyone can form $E(a/b)$ using the homomorphic property of El Gamal. Suppose $E(a/b)=(r,s)=(g^k,h^k a/b)$ (where $g$ is the generator and $h$ is the public key). Then proving that $a=b$ is equivalent to proving that $a/b=1$, i.e., that $(r,s)=(g^k,h^k)$ for some $k$, or in other words, that $(g,h,r,s)$ is a Diffie-Hellman 4-tuple. There is a standard zero-knowledge protocol to prove this fact. That's all you need.

  • 2
    $\begingroup$ That is a cool construction. You could do the same thing with Paillier. Prove that $E(a-b)=0$. My thep library has a ZKP for set membership which should serve that purpose well (use a set of just $0$). $\endgroup$
    – mikeazo
    Commented Oct 12, 2012 at 11:57

You are in a twist here:

  • semantic security (equal to IND-CPA) can only be fulfilled by probabilistic encryption schemes.
  • You need a deterministic encryption scheme for your drop-out tolerance.

As it was pointed out previously, any homomorphic encryption allows you to proof in zero knowledge the equality of two ciphertexts:

  • known: $c_0 = E(x,r_0)\;,\;c_1 = E(x,r_1)$
  • Prover: commits $c_2 = E(x,r_2)$
  • Verifier: flip a coin for bit $b$.
  • Prover: decommit $(c_2 - c_b)$ by showing the according random coin $r_d$ (this is usually $r_d = r_2 - r_b$)
  • Verifier: check if $E(0,r_d) = c_2 - c_b$. ('0' stands for the neutral element)

With deterministic encryption it is trivial, two plaintexts are equal if and only if their ciphertexts are equal. But this is not IND-CPA.


With any convergent encryption algorithm E, it's easy for Alice to prove -- without revealing(*) a, b or the private key -- that a == b.

In order for the data deduplication feature to work, convergent algorithms are specifically designed such that when Alice encrypts two messages a and b, such that x=E(a), y=E(b), then x == y whenever a == b.

There's some discussion here under the tag and on other stackexchange sites. ( "Online backup : how could encryption and de-duplication be compatible?" ).

(*) Alas, if b is "small", or if enough is known about b that the remaining unknown portion is "small", most convergent encryption algorithms allow some attacker to reveal b by exhaustively enumerating all possible messages m, until the attacker finds some message where y = E(b) == z = E(m), and therefore the attacker has revealed that b == m. In particular, for Mental Poker, if Alice sets "b" to be some 2-byte representation of a single card, then publishes y = E(b), Mallory could probably discover which particular card pretty rapidly.

Fortunately, in practice, it's often possible to make b large enough and with enough unknowns that it is impractical to apply this attack. In particular, for Mental Poker, If Alice sets "c" to a freshly-generated 256-bit random number concatenated with some 2-byte representation of a single card, then publishes w = E(c), it appears to be infeasible for Mallory to gain any more information about which card c that Alice picked.

  • $\begingroup$ Alas, if that is done, then it is no longer simple to prove -- without revealing the 256-bit random $\hspace{0.8 in}$ number or the private key -- that the cards represented are equal. $\:$ $\endgroup$
    – user991
    Commented Oct 16, 2012 at 19:14
  • $\begingroup$ @RickyDemer: I'm no poker expert, but I don't follow. If Alice wants to prove that message A (the ace of hearts with a freshly-generated 256-bit random number) is the same as message B (also the ace of hearts with the same 256-bit random number), can't she simply point out that X and Y are identical, without revealing the 256-bit random number or her private key or the fact that A represents the ace of hearts? $\endgroup$
    – David Cary
    Commented Oct 17, 2012 at 14:43
  • $\begingroup$ Yes, but using the same 256-bit random number to get ciphertext B would mean that the 256-bit random number used to get ciphertext B was not fresh. $\:$ (And now a see that I'd accidentally typed "number" in my first comment, instead of "numbers".) $\;\;$ $\endgroup$
    – user991
    Commented Oct 17, 2012 at 17:38

This question was asked in 2012, and it's a good example of how zk proof technology has improved in the subsequent decade or so. In 2024 the answer can be straightforwardly: use a general-purpose zk-SNARK such as PLONK or Halo 2 to prove the statement $$\{ (x, y, pk): \exists (r, r', a) \text{ such that} \\ E_{pk,r}(a) = x \wedge E_{pk,r'}(a) = y \}$$ directly for any, in principle arbitrary, public key encryption scheme. ($r$ and $r'$ here are the random inputs to each encryption. In practice you also want to be explicit about the types when instantiating this for a particular $E$.)

That's not to say it's trivial: the circuit will be more efficient and easier to audit if the encryption scheme and zk-SNARK parameters are chosen to make it easier to express the encryption (for example, if $E$ is an elliptic curve encryption scheme using an embedded curve for the proof system). And it is still the case that a specialized encryption scheme and specialized proof, as suggested in the other answers, could be more efficient.

On the other hand, a general-purpose zk-SNARK comes into its own in terms of extensibility: we can relatively easily add constraints to the statement that would be all-but-impossible for a specialized construction.


Your Answer

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

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