6.897: Advanced Topics in Cryptography Feb 5, 2004Lecture 3,4: Universal ComposabilityLecturer: Ran Canetti Scribed by: Yael Kalai and abhi shelat1 IntroductionOur goal in these two lectures is to prove the Composition Theorem that was presented at the endof the previous lecture, and to show how it can be applied it to the zero-knowledge functionality.As an example of the latter, we present the Blum Hamiltonicity protocol and discuss some issuesrelated to parallel composition.2 Composition TheoremLet P be a protocol that securely realizes a function f. Let Q be a protocol in the f-hybrid model.Recall that the protocol QPis the composition protocol in which each call to f is replaced by aninvocation of P , and P ’s outputs are treated as the outputs of f.Theorem 1 (The Composition Theorem): Protocol QP“emulates” protocol Q. That is, for anyB-limited adversary A, there is a B-limited adversary H such that for any any Z we have:EXECfQ,H,Z∼ EXECQp,A,ZWe refer the reader to the previous lecture notes for notations and definitions.3 Proof of the Composition TheoremLet A be any B-limited adversary that interacts with protocol QPin the real-life model. Our goalis to construct a B-limited adversary H that interacts with protocol Q in the f-hybrid model, suchthat no environment Z can tell the difference between the two interactions. We will construct Hvia the following three steps.1. From A we construct an adversary APthat interacts only with protocol P .2. From the security of P , there is an adversary SPin the ideal process for evaluation of f, suchthat for every environment Z, IDEALfSP,Z∼ EXECP,AP,Z.3. We use A and SPto construct an adversary H and show that for every environment Z,EXECfQ,H,Z∼ EXECQP,A,Z.3,4-13.1 Adversary APWe will use APonly when inte racting with an environment Z, that gives APan input which consistsof the internal state of A at the beginning of the round where protocol QPcalls P . Thus, we willdefine AP’s behavior only with respect to such inputs. (If the input is of any other format then APhalts.)AP, on input an internal state of A at the beginning of the round where protocol QPcalls P ,will run A from this state, while interacting with P . At the end of the run, APwill output thecurrent state of A.From the security of P , we know that there exists an adversary SPsuch that for every environ-ment Z, IDEALfSP,Z∼ EXECP,AP,Z.3.2 Adversary HNow we will use A and SPto define an adversary H, which interacts with Q in the f-hybrid model.1. Until the round where all parties in Q call f, run A. (Indeed, up to this point the protocolsQ and QPare identical.)2. At the point where Q calls f, run SPwith the current state of A as input. When SPgeneratesf-inputs for the corrupted parties, forward these inputs to f (Recall that SPis an adversaryin the ideal process for f). Finally, forward to SPthe outputs that the ideal process f givesto the corrupted parties.3. Once SPgenerates an output, which consists of an internal state of A (follows form thedefinition of APand from the fact that P securely realizes f), continue running A from thisstate.4. Halt when A halts, and output whatever A outputs.This C ompletes the definition of H.3.3 Analysis of HOur goal is to prove that for every environment Z, EXECfQ,H,Z∼ EXECQP,A,Z. We will provethis by contradiction, as follows. Assume that there exists an environment Z that, on input z,distinguishes (with non-negligible probability) between a run of H with Q in the f-hybrid modeland a run of A with QPin the plain real-life model. We will construct an environment ZPthat,on input z, distinguishes with the same probability between a run of SPwith the ideal process forf and a run of APwith P . This will contradict the assumption that P securely realizes f.The environment ZP, on input z, will operate as follows:1. Run Z on input z, and orchestrate for Z an interaction of parties running QPwith adversaryA, until the round where P is called.2. At the round where P is called, start interacting with the external system, by giving theexternal good parties the inputs that the simulated good parties would give to P , and bygiving the external adversary the current state of A.3,4-23. Upon receiving the external outputs from the parties and the adversary, continue the simu-lated interaction between A and the parties running QP– The good parties use their outputsfrom the external s ystem as the outputs of P , and A runs from the state given in the outputof the external adversary.4. When the internal outputs are generated, hand them to Z, and output whatever Z outputs.Notice that if the “external system” that ZPinteracts with is an ideal process for f withadversary SPthen the simulated Z sees exactly the interaction with H and Q in the f-hybridmodel. If the “external system” that ZPinteracts with is an execution of P with adversary AP,then the simulated Z sees exactly an interaction with A and QPin the plain real-life m odel. Thus,ZPdistinguishes with the same probability that Z distinguishes.4 Implication of the Composition TheoremThe main implication of Composition Theorem is that using the our notion of security composes.In other words, it enables us to des ign and analyze protocols in a modular way:1. Partition a given task T to simpler sub-tasks T1, . . . , Tk.2. Construct protocols for realizing T1, . . . , Tk.3. Construct a protocol for T assuming ideal access to T1, . . . , Tk.4. Use the composition theorem to obtain a protocol for T from scratch.Thus far, we formally defined what it means for a protocol to securely realize a function f,and we proved the Composition Theorem, which shows that this definition has a nice compositionproperty. We would like to demonstrate the usefulness of such a definition. As a first step, wewill use this heave machinery to prove that zero-knowledge protocols compose sequentially, a resultwhich is well known and relatively easy to prove directly.In order to prove that zero-knowledge protocols compos e sequentially, we will first define zero-knowledge in a “secure function evaluation” style, and show that it is essentially equivalent to thestandard definition.5 Zero-Knowledge Proofs [GMR89]We begin by defining the notion of computational indistinguishability, which will be used in ourdefinition of zero-knowledge.Definition 1 Distribution ensembles D and D0are computationally indistinguishable (denoted byD ≈ D0) if for any polynomial time distinguisher A, for all c, d, and for all large