6.897: Selected Topics in Cryptography Lectures 7 and 8Highlights of past lecturesLectures 7 and 8 The UC Framework and composition theoremPowerPoint PresentationSlide 5Characteristics of the basic definitionWish-list for a more general frameworkPresenting the UC frameworkSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17VariantsEquivalent formulations (same as for the basic definition):Another equivalent formulation: security w.r.t. a dummy adversarySlide 21Slide 22The UC theoremModular composition: The basic idea for a single copy of fThe basic idea for multiple calls to F:Slide 26Slide 27The composition operation: universal composition (Originates with [Micali-Rogaway91])Slide 29Implications of the UC theoremSlide 31Slide 32Slide 33Slide 34Some ideal functionalities“standard” ideal functionalities:Example: The authenticated message transmission functionality, FauthExample: The secure message transmission functionality, FsmtExample: The key-exchange functionality FKE (I)Example: The key-exchange functionality FKE (II)Example: The ZKPoK functionality Fzk (for relation R),Example: The commitment functionality, FcomExample: The Synchronous Communication Functionality, Fsynch (parameterized by a set T of PIDs of participants)Slide 446.897: Selected Topics in CryptographyLectures 7 and 8Lecturers: Ran Canetti, Ron RivestScribes?Highlights of past lectures• P resented a basic framework for analyzing the security of protocols for multi-party function evaluation.•Presented the notion of modular composition.• S tated and proved the non-concurrent. composition theorem•Showed how to capture ZK and PoK within this framework.• Used the composition theorem to analyze a basic ZK protocol.•Mentioned some limitations of the notion…•Lectures 7 and 8The UC Framework and composition theorem•Motivation for a new framework•The UC framework:–The basic system model–The real-life model for protocol execution–Ideal functionalities and the ideal process•Alternative formalizations•Universal composition:–The hybrid model–The composition operation–The UC theorem–Interpretations–Proof•Some ideal functionalitiesReview of the definition:P1P3P4P2FP1P3P4P2SAZProtocol P securely realizes F if: For any adversary A There exists an adversary S Such that no environment Z can tell whether it interacts with: - A run of with A - An ideal run with F and SZIdeal process:Protocol execution:Note:There exist protocols for securely evaluating any multi-party function under this definition:–Goldreich-Micali-Wigderson [GMW87,G98,G04], for any number of faults, computational.–BenOr-Goldwasser-Wigderson [BGW88], for honest majority, algebraic, “information-theoretic”.–Many other protocols…Characteristics of the basic definition•Simplistic system model: Fixed set of parties, fixed identities, fixed number of protocols. •Fixed set of corrupted parties.•Only function evaluation.•Environment interacts with the computation only at the beginning and the end. •Only non-concurrent composition.Wish-list for a more general framework•Deal with more “real-life” settings such as:–Asynchronous communication–Unreliable and unauthenticated communication–Variable (even unbounded) number of participants–Variable identities•Deal with reactive tasks (e.g., encryption, signatures, commitments, secret-sharing…)•Deal with adaptive break-ins to parties•Deal with concurrent composition•Allow proving security of “natural protocols” The UC framework is aimed at all of the above goals (except perhaps the last one… but not really)Presenting the UC framework•Generalize the underlying computational model (“systems of ITMs”)•Generalize the real-life model of protocol execution•Generalize the notion of a “trusted party” and the ideal process•Generalize the notion of protocol emulation•Interactive Turing machines (ITMs): An ITM is a TM with some special tapes:–Incoming communication tape–Incoming subroutine output tape–Identity tape, contains ID=(SID,PID), where:• SID is the “session ID” • PID is the “party ID”–security parameter tapeAn activation of an ITM is a computation until a “waiting” state is reached.•Polytime ITMs: An ITM M is polytime if at any time the overall number of steps taken is polynomial in the security parameter plus the overall input length (ie, # of bits on the input tape).Systems of interacting ITMs (Variable number of ITMs):A system of interacting ITMs is a pair (M0,C) where is the initial ITM and C is a “control function” from sequences of requests to {0,1}. A run of the system is the following process:• M0 starts with some external input and value for the security parameter.• In each activation an ITM may request to write to at most one tape of another ITM. A request includes:–Identity of the requesting ITM–Identity of the target ITM and tape, code for the target ITM.–Contents If the control function C allows the tuple (source id, target id, code, tape) then the instruction is carried out. If no ITM with target id exists then a copy is invoked, with said code, identity, and sec. param. • The machine written to is the next to be activated. If none then M0 is activated next.• The output is the output of the initial ITM M0. Notice: the identity of each ITM is globally unique.•Convention: If an ITM M is invoked because M’ wrote to its input tape then M is called a subroutine of M’ and M’ is the invoker of M. •States of systems of ITMs–:A state of a system describes an instance in the run of the system, including local states of all ITMs.•Multi-party protocols: –A multi-party protocol is a (single) ITM.–An instance of a protocol P with SID sid, in a state s of a system, is the set of all ITMs in s whose code is P and whose SID is sid.(some technicalities are pushed under the rug…)The “real-life model” for protocol executionThe real-life model for executing P with environment Z is the following system of interacting ITMs:•Initial ITM:–Environment Z (the initial ITM, with fixed ID)•Control function:–Z can activate a (single copy of) an ITM A (adversary), and multiple ITMs running P, all having the same SID, and write to their input tapes. –A can write to the incoming comm. tapes of all parties and to the subroutine output tape of Z.–All other ITMs can write to the