6.897: Selected Topics in Cryptography Lectures 11 and 12Highlights of last week’s lecturesThis week:UC Zero-Knowledge from UC commitmentsThe ZK functionality Fzk (for relation H(G,h)).The ZK functionality with weak soundness, Fwzk (for relation H(G,h)).The Blum protocol in the Fcom-hybrid model (“single iteration”)PowerPoint PresentationSlide 9Slide 10From FwzkR to FzkRAnalysis of the protocolSlide 13How to realize any two-party functionalityHow to realize any two-party functionality: The [GMW87] paradigmSlide 16The semi-honest, two-party caseThe semi-honest adversarial modelThe (1-out-of-m) oblivious transfer functionality, FOTm.Realizing FOT2 (the [EGL85] protocol)Slide 21Slide 22Evaluating general functionalities in the semi-honest, two-party caseThe protocol in the FOT-hybrid modelSlide 25Slide 26Slide 27Slide 28[GMW87] Protocol CompilationConstructing a UC “[GMW87] compiler”The “Commit&Prove” primitiveThe Commit&Prove functionality, Fcp (for relation R)Realizing FcpR in the Fzk-hybrid modelSlide 34Slide 35The compiler in the Fcp-hybrid modelSlide 37Extension to the multiparty case: ChallengesExtension to the multiparty case: The semi-honest protocol (fixed set of n parties)Extension to the multiparty case: Byzantine adversariesExample: The 1:M commitment functionality, Fcom1:MHonest majority: Can do without the CRSSlide 436.897: Selected Topics in CryptographyLectures 11 and 12Lecturers: Ran Canetti, Ron RivestScribes?Highlights of last week’s lectures• Formulated the ideal commitment functionality for a single instance, Fcom.• S howed that it’s impossible to realize Fcom in the plain model (even when given ideal authentication).• Formulated the “CRS model” as the Fcrs-hybrid model.• S howed how to realize Fcom in the Fcrs-hybrid model.• S howed how to do multiple commitments with the same CRS:–Formulated the multi-instance ideal commitment functionality, Fmcom.–Showed how to realize Fmcom given a single copy of Fcrs.•This week:•Show how to obtain UC ZK from UC commitments (this is “easy”, or “information-theoretic”)• Show how to realize any multi-party functionality, for any number of faults, in the Fcrs-hybrid model (using the [GMW87] paradigm).•Mention how can be done in the plain model when there is honest majority (using elements from [BGW88]).•UC Zero-Knowledge from UC commitments•Recall the ZK ideal functionality, Fzk, and the version with weak soundness, Fwzk. •Recall the Blum Hamiltonicity protocol•Show that, when cast in the Fcom-hybrid model, a single iteration of the protocol realizes Fwzk. (This result is unconditional, no reductions or computational assumptions are necessary.)•Show that can realize Fzk using k parallel copies of Fwzk.The ZK functionality Fzk (for relation H(G,h)). 1. Receive (sid, P,V,G,h) from (sid,P). Then:1. Output (sid, P, V, G, H(G,h)) to (sid,V)2. Send (sid, P, V, G, H(G,h)) to S3. Halt.The ZK functionality with weak soundness, Fwzk (for relation H(G,h)). 1. Receive (sid, P, V,G,h) from (sid,P). Then:1. If P is uncorrupted then set vH(G,h). 2. If P is corrupted then:•Choose bR {0,1} and send to S. •Obtain a bit b’ and a cycle h’ from S.•If H(G,h’)=1 or b’=b=1 then set v1. Else v0. 3. Output (sid, P, V, G,v) to (sid,V) and to S.4. Halt.The Blum protocol in the Fcom-hybrid model (“single iteration”)Input: sid,P,V, graph G, Hamiltonian cycle h in G.•P  V: Choose a random permutation p on [1..n]. Let bi be the i-th bit in p(G).p. Then, for each i send to Fcom: (sid.i,P,V,“Commit”,bi) .•V  P: When getting “receipt”, send a random bit c.•P  V: If c=0 then open all commitments (I.e., send Fcom: (sid.i,“Open”) for all I). If c=1 then open only commitments of edges in h.•V accepts if all the commitment openings are received from Fcom and in addition:–If c=0 then the opened graph and permutation match G–If c=1, then h is a Hamiltonian cycle.Claim: The Blum protocol securely realizes FwzkH in the Fcom–hybrid model Proof sketch: Let A be an adversary that interacts with the protocol. Need to construct an ideal-process adversary S that fools 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 (G,”reject”) to A. If value from Fzk is (G,1) then simulate an interaction for V:•For all i, send (sid_i, “receipt”) to A.•Obtain the challenge c from A.•If c=0 then send openings of a random permutation of G to A•If c=1 then send an opening of a random Hamiltonian tour to A. The simulation is perfect…2. A controls the prover (weak extraction): S gets input z’ from Z, and runs A on input z’. Next: I. Obtain from A all the “commit” messages to Fcom and record the committed graph and permutation. Send (sid,P,V,G,h=0) to Fwzk. II. Obtain the bit b from Fwzk. If b=1 (i.e., Fwzk is going to allow cheating) then send the challenge c=0 to A. If b=0 (I.e., no cheating allowed) then send c=1 to A. III. Obtain A’s opening of the commitments in step 3 of the protocol. If c=0, all openings are obtained and are consistent with G, then send b’=1 to Fwzk . If some openings are bad or inconsistent with G then send b’=0 (I.e., no cheating, and V should reject.) If c=1 then obtain A’s openings of the commitments to the Hamiltonian cycle h’. If h’ is a Hamiltonian cycle then send h’ to Fwzk. Otherwise, send h’=0 to Fwzk .Analysis of S: (A controls the prover): The simulation is perfect. That is, the joint view of the simulated A together with Z is identical to their view in an execution in the Fcom –hybrid model:–V’s challenge c is uniformly distributed.–If c=0 then V’s output is 1 iff A opened all commitments and the permutation is consistent with G.–If c=1 then V’s output is 1 iff A opened a real Hamiltonian cycle in G.3. A controls neither party or both parties: Straightforward.4. Adaptive corruptions: Trivial… (no party has any secret state).From FwzkR to FzkRA protocol for realizing FzkR in the FwzkR -hybrid model:•P(x,w): Run k copies of FwzkR , in parallel. Send (x,w) to each copy.•V: Run k copies of FwzkR , in parallel. Receive (xi,bi) from the i-th copy. Then:–If all x’s are the same and all b’s are the same then output (x,b).–Else output nothing.Analysis of the