6.897: Selected Topics in Cryptography Lectures 7 and 8 Lecturer: Ran CanettiHighlights of past lectures • Presented a basic framework for analyzing the security of protocols for multi-party functionevaluation. • Presented the notion of modular composition. • Stated 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 8 The 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 functionalitiesP1 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: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 tape An 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 execution The 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 incoming comm. tape of A, can invoke new ITMs, and can write to the subroutine output tape of their invoker and the input tapes of their subroutines. – Modeling corruptions: A can write a “corrupt” message on incoming comm. Tape of ITM M. Then: • M writes “Corrupted” on subr. output tape of Z • From now on, in each activation M sends its entire state to A • A assumes all write privileges of M.•Notes: – Z interacts with A freely throughout the computation. – All communication between parties is done “via A”. – Asynchronous communication, no authenticity/reliability guarantee. – Z creates new parties adaptively, sets their identities. – Adaptive corruptions. • Notation: – EXECP,A,Z (k,z,r) : output of Z after above interaction with P,A, on input z and randomness r for the parties with s.p. k. (r denotes randomness for all parties) – EXECP,A,Z (k,z) : The output distribution of Z after above interaction with P,A, on input z and s.p. k, and uniformly chosen randomness for the parties. – EXECP,A,Z : The ensemble of distributions {EXECP,A,Z (k,z)} k in N, z in