1 6.879 Special Topics in Cryptography Instructor: Ran CanettiLecture 20: Verifiable Mix-Nets April 16, 2004 Scribe: Matt Lepinski Two-By-Two Verifiable Mixes Before solving the general case of verifiably mixing n ciphertexts, we first consider the case of a verifiable two-by-two with two incoming ciphertexts, C1 and C2 and two outgoing ciphertexts C�and C2�. In this case, what the mixer must prove is that:1 1 (C1 ≈ C1�) ∧ (C2 ≈ C2�) ∨ (C1 ≈ C1�) ∧ (C2 ≈ C1�) This is equivalent to proving: [(C1 ≈ C1�)∨ (C1 ≈ C2�)]∧ [(C2 ≈ C1�)∨ (C2 ≈ C2�)]∧ [(C1�≈ C1)∨ (C1�≈ C2)]∧ [(C2�≈ C1)∨ (C2�≈ C2)] Observed that the above expression is a conjunction of four disjunctions. We will give a protocol which allows the prover to prove a single disjunction. The prover can then prove the entire expression by separately proving that each of the four disjunctions is true. First we recall from last lecture the Chaum-Pedersen honest zero knowledge protocol for proving that two El Gamal ciphertexts, C1 = (α1, β1) = (gt, m1 · yt) and C�= (α1�, β1�)1 = (gu, m�1 · yu) have the same plaintext (where the prover knows the re-encryption factor, v = u− t).2 Let (a1, a2, b1, b2) be the quadruple (g, y, (α1�/α1), (β1�/β1)) = (g, y, gThen m1 v , (m1�/m1)· yv ). = m2 if and only if loga1 (b1) = loga2 (b2) = v. (Proof left as an easy exercise.) To prove equality, use the following protocol: P V randomly select from ∗Zsq ¯ ¯: A = ( A¯ 1, A2) = (a←− c )s−→ 2s, a1: randomly select from ∗Zcq r = s + c ∗ v : r −→ Accept if a r 1 = A1bc 1 and a r 2 = A2bc 2 (This is really two parallel instances of the previous Chaum-Pedersen protocol, sharing r and c. Although we don’t need this fact here, this protocol could be showing equality of logarithms in two distinct groups.) The protocol is honest-verifier zero-knowledge; it is also a proof of knowledge of v. Moreover it is “special HVZK”: given any specific c, one can ¯pick A and r to match the conditional distribution of the transcripts, given c. We now present an honest zero-knowledge protocol for proving the disjunction [(C1 ≈C1�) ∨ (C1 ≈ C2�)] (where the prover knows either the first re- encryption factor r1 or the 1Recall that we denote the relation “C has the same plaintext as D” by writing C ≈ D. 2Here we assume that g is a publically known generator of Zq ∗ . Lecture 20-1� � � second re-encryption factor r2):3 This protocol is derived from the paper by Cramer et al. [CDS94]. P V ¯ ¯ A1, A2 −→ ←− c : randomly select c r1, r2, c1, c2 −→ The verifier accepts if (1) the Chaum-Pedersen verifier would accept the triple ( ¯ A1, c1, r1) with ciphertexts C1 and C1�(2) the Chaum Pedersen verifier would accept the triple ( ¯ A2, c2, r2) with ciphertexts C1 and C2�and (3) c = c1 ⊕ c2. Completeness: Without loss of generality, we consider the case where the prover knows first read encryption factor r1. The prover then runs the Chaum-Pedersen simulator for ¯ciphertexts C1 and C2�to obtain the triple ( ¯ A2, c2, r2). The prover then chooses A2 as the ¯ ¯honest prover would in the Chaum-Pedersen protocol and sends A1, A2 to the verifier. Upon receiving, challenge c from the verifier, the prover chooses c1 so that c = c1 ⊕ c2 and computes the response r1 to challenge c1 as the honest prover would in the Chaum-Pedersen protocol. The verifier will accept because ( ¯ A1, c1, r1) are constructed honestly as in the Chaum-Pedersen protocol and ( ¯ A2, c2, r2) are constructed by the Chaum-Pedersen Simulator. That is, the verifier accepts ( ¯ A1, c1, r1) because the Chaum-Pedersen protocol is complete and the verifier accepts ( ¯ A2, c2, r2) because the Chaum-Pedersen protocol is honest zero-knowledge. Soundness: Recall that the “special” soundness of the Chaum-Pedersen protocol implies ¯that if for some A you have more than one valid c, r pair then you can extract a witness to the fact that the two ciphertexts have the same plaintext (in particular, the re-encryption factor). If in the above protocol the prover can answer some � fraction of possible challenges where � is non-negligible, then one can sample random challenges c and in polynomial time find a pair of challenges c =� c� such that the prover correctly answers responds to both c and c�. Since c = c1 ⊕ c2 and c� = c�1 ⊕ c2�and c = c� then either c1 = c1�or c2 = c�. Therefore 2one can extract either a witness that C1 ≈ C1�or a witness that C1 ≈ C2�and hence the disjunction [(C1 ≈ C1�) ∨ (C1 ≈ C2�)] must be true. Honest Zero-Knowledge: The simulator picks c1 and c2 independently at random and ¯selects c so that c = c1 ⊕ c2. The simulator then constructs A1 and r1 corresponding to challenge c1 in the same way that the Chaum-Pedersen simulator would. Similarly, the ¯simulator c onstructs A2 and r2 corresponding to challenge c2 in the same way that the Chaum-Pedersen simulator would. Observe that since c1 and c2 are chosen independently, c is a random element of Zq ∗ . Remark: In the above protocol, one can interpret c1 and c2 as a sharing of secret c. This is a special case of a general connection between secret sharing schemes and proofs of monotone Boolean formulas. See [CDS94] for more details. Here we denote by ⊕ the operation of addition in the ring Zq ∗. Lecture 20-2 3Remark: Since the above protocol is honest zero knowledge, it is also witness indistinguish-able. Recall the witness indistinguishable proofs can be com posed in parallel and remain witness indistinguishable. 2 Going From 2 to n Here we use sorting networks to build an n by n verifiable mix from many 2 by 2 verifiable mixes. 4 A sorting network is a circuit with n input wires and n output wires consisting of 2 by 2 comparator gates. The operation of a comparator is as follows: If the two input wires have values x and y then the comparator outputs max(x, y) on the “top” output wire and min(x, y) on the “bottom” output wire. x − − − −− ◦ − − − − − max(x, y) | | | y − − − −− ◦ − − − − − min(x, y) Such a network of comparators is a valid sorting network if for any possible set of values on the n input wires, the values on the n output