# Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts?

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 need 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.

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

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.

-
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$). –  mikeazo Oct 12 '12 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.

-
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. $\:$ –  Ricky Demer Oct 16 '12 at 19:14
@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? –  David Cary Oct 17 '12 at 14:43
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".) $\;\;$ –  Ricky Demer Oct 17 '12 at 17:38