6.897: Selected Topics in Cryptography Lecturer: Ran CanettiLectures 3 and 4: ZK as function evaluation and sequential composition of ZK • Review the definition of ZK and PoK • Give SFE-style definition of ZK and show equivalence to the standard one. • The Blum protocol for Hamiltonicity: – Commitment schemes – The protocol – Analysis of a single instance: Weak soundness – Analysis of the iterated protocol using the composition theorem.P1 P3 P4 P2 F P1 P3 P4 P2 S A Protocol execution: whether it interacts with: - A run of π with A - An ideal run with F and S Z Protocol P securely realizes F if: For any adversary A There exists an adversary S Such that no environment Z can tell ZIdeal process: Review of the definition:Review: Zero-Knowledge [Goldwasser-Micali-Rackoff 85] Let R(x,w) be a polytime relation. A ZK protocol for R is a protocol for two parties P,V, where P has (x,w), V has no input, and the following holds: • Completeness: Prob[(P(x,w),V)=(x,R(x,w))]~1(if P,V are honest then V outputs x and the value of R(x,w)) • Soundness (I): For all P* and all z, Prob[(P(z),V)=(x,1) ^ (R(x,w)=0 for all w )]~0 Differences from the standard definition: 1. In the standard def, V has x as input, whereas here V has no input and instead itoutputs P’s input x. (But it is easy to translate a protocol from one def to the other.) 2. The standard definition of ZK doesn’t make any completeness requirement whenR(x,w)=0. Here we require that V outputs (x,0). (But this is easy to achieve, by having P send (x,”reject”) to V.)Review: Zero-Knowledge [Goldwasser-Micali-Rackoff 85] • Zero-Knowledge: For any verifier V* there exists a machine S such that for all x,w,z, S(x,R(x,w),z) ≈ V*P(x,w)(z). “Whatever V* can gather from interacting with P, it could havecomputed by itself given R(x,w).” (Distribution ensembles D,D’ are computationally indistinguishable (written D ≈ D’) if for any polytimedistinguisher A, for all c,d, large enough k, and a with |a|< kd, ProbxÅDk,a[A(1k ,a,x)=1]- ProbxÅD’k,a[A(1k ,a,x)=1]< 1/kc )Review: Proof of Knowledge [Goldwasser-Micali-Rackoff, Goldreich-Oren, Tompa-Woll, Bellare-Goldreich, Halevi-Micali, Lindell, …] Let R(x,w) be a polytime relation. A PoK protocol for R is a protocol for two parties P,V, where P has (x,w), and thefollowing holds: • Soundness (II), or “extractability”: For any prover P* there exists a “knowledge extractor” E, such that for any z, we have E(z) = (t,x*,w*) and t,(x*,R(x*,w*)) ≈ AT(P*(z),V)), where AT is the “augmented transcript” of an execution of (P*(z),V)),namely the sequence of exchanged messages, plus the output of V. “V is assured that, in each accepting interaction, it is possible to explicitly extract the witness from the prover’s input. Furthermore, the extracted witness is the “appropriate witness” for this interaction.” (This specific formulation is in the spirit of the “enhanced PoK” of [Lindell 03].)ZK PoK as an SFE task FLet R(x,w) be a binary relation. Consider the 2-party function:zkR ((x,w), - , - ) = ( - , (x,R(x,w)) , (x,R(x,w))) Theorem: A two-party protocol securely realizes FzkR (with respect to non-adaptive adversaries) if and only ifit is a ZK PoK for R. Proof: Homework.Example: Blum’s protocol for Graph Hamiltonicity [Blum 8?]Commitment schemes Intuitive idea [Blum 82]: Commitment is a two-party, two-step process: – Commitment, where the committer C gives a value x to thereceiver V “in an envelope” – Decommitment, where C “opens” the envelope for V. We want to guarantee: – Secrecy: at the end of the commitment step V “has no knowledge” of what x is. – Binding: Once the commitment step is done, there is asingle value x fixed, such that C can successfullydecommit only the value x.Commitment schemes: A formalization A basic formalization (commitments for one bit): A tuple (C,D ,Vc,Vd) of ITMs is a bit commitment scheme if: • Completeness: For all b in {0,1},Prob[(C(b),Vc)Æ(sc,sv), (D(sc),Vd (sv))Æ(-,b)] ~ 1 ≈• Secrecy: For all V*, (C(0),V*) (C(1),V*). • Binding: For all C*,D*, Prob[(C*,Vc)Æ(sc,sv),(D*(sc,0),Vd(sv))Æ(-,0),(D*(sc,1),Vd(sv))Æ(-,1)] ~ 0The basic Blum protocol Common relation: HC(G,H)=1 if H is a Hamiltonian cycle in graph G. Common input: k-node graph G Secret witness for P: Hamiltonian cycle H in G. • P(G,H): If HC(G,H)=0 then send (G,”reject”) to V. Else, choose arandom permutation p on [1..k] and send (G, C(p(G)), C(p)) to V. •V: If received (G,”reject”) then output (G,0). Else, send a randombit b to P. •P: If b=0 then decommit to all commitments of message 1. If b=1 then open only the commitments of the edges in H. •V: Accept (output (G,1)) if all the commitment openings areaccepted and, if b=1, then also if H is a Hamiltonian cycle.Else reject (output (G,0)).Towards analysis… HCWant to show that the protocol realizes Fzk . But clearly it does not: It has a soundness error of ½. • Question: How to achieve full soundness, and in particular obtain a PoK? • Basic idea: repeat many times, and have the verifier accept if all repetitions succeed. The hope is that ZK will be preserved, and soundness error will diminish. • Questions: – How to repeat? (sequentially? In parallel?) – How to analyze?We show that sequential repetition works. Traditionally, this is proven directly. We’ll use the composition theorem. Plan: – Define a “ZK with weak PoK functionality,” Fwzk, and show that the basic protocol realizes it. – Show how to realize Fzk in the Fwzk-hybrid model. – Use the composition theorem to deduce security of the composed protocol.The “ZK with weak PoK” functionality • Idea: Relax Fzk to allow the adversary to break soundness w.p. up to ½. Let R(x,y) be a binary relation. Recall: FzkR ((x,w), -,- ) = ( - ,(x,R(x,w)),(x,R(x,w))) • Define: FwzkR ((x,w), -,c) = If R(x,w)=1 then output (-,(,x,1),(x,1). Else, if c=“no cheat” output (,(,x,0),(x,0)). If c=“cheat” output (,(,x,b),(x,b)) for bÅ R {0,1}.H Claim: The basic Blum protocol securely realizes Fwzk . Proof sketch: Let A be an adversary that interacts with theprotocol. Need to construct an ideal-process adversary S thatfools all environments. There are four cases: 1. A controls the verifier (Zero-Knowledge): S gets input z’ from Z, and runs A on input z’. Next: – If value from Fzk is (G,0) then hand