Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this 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
add comment

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
2  
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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