6.897: Advanced Topics in Cryptography Lecturer: Ran CanettiFocus for first half (until Spring Break): Foundations of cryptographic protocols Goal: Provide some theoretical foundations of secure cryptographic protocols: • General notions of security • Security-preserving protocol composition • Some basic constructions Overall: Definitional and foundational slant (but also constructions, and even some efficient ones…)Notes • Throughout, will try to stress conceptual points and considerations, and will spend less time on technical details. • Please interrupt me and ask lots of questions – both easy and hard! • The plan is only a plan, and is malleable…Lecture plan Lecture 1 (2/5/4): Overview of the course. The definitional framework of “classic” multiparty function evaluation (along the lines of [C00]): Motivation for the ideal-model paradigm. The basic definition. Lecture 2 (2/6/4): Variants of the basic definition. Non-concurrent composition. Lecture 3 (2/12/4): Example: Casting Zero-Knowledge within the basic definitional framework. The Blum protocol for Graph Hamiltonicity. Composability of Zero-Knowledge. Lecture 4 (2/13/4): The universally composable (UC) security framework: Motivation and the basic definition(based on [C01]). Lectures 5,6 (2/19-20/4): No lecture (TCC)Lecture 7 (2/26/4): Alternative formulations of UC security. The universal composition theorem. Survey of feasibility results in the UC framework. Problem Set 1. Lecture 8 (2/27/4): UC commitments: Motivation. The ideal commitment functionality. Impossibility of realizations in the plain model. A protocol in the Common Reference String (CRS) model (based on [CF01]). Lecture 9 (3/4/4): The multi-commitment functionality and realization. UC Zero Knowledge from UC commitments. Universal composition with joint state. Problem Set 1 due. Lecture 10 (3/5/4): Secure realization of any multi-party functionality with any number of faults (based on [GMW87,G98,CLOS02]): The semi-honest case. (Static, adaptive, two-party, multi-party.)Potential encore: On symbolic (“formal-methods”) analysis of cryptographic protocols.Lecture 11 (3/11/4): Secure realization of any multi-party functionality with any number of faults: The Byzantine case. (Static, adaptive, two-party, multi-party.) The case of honest majority. Lecture 12 (3/12/4): UC signatures. Equivalence with existential unforgeability against chosen message attacks (as in [GMR88]). Usage for certification and authentication. Lecture 13 (3/18/4): UC key-exchange and secure channels. (Based on [CK02]). Lecture 14 (3/19/4): UC encryption and equivalence with security against adaptive chosen ciphertext attacks (CCA). Replayable CCA encryption. (Based on [CKN03].) Problem Set 2.Scribe for today?What do we want from a definition of security for a given task? • Should be mathematically rigorous (I.e., should be well-defined how a protocol is modeledand whether a given protocol is “in” or “out”). • Should provide an abstraction (“a primitive”) that matches our intuition for the requirements of the task. • Should capture “all realistic attacks” in the expected execution environment. • Should guarantee security when the primitive is needed elsewhere. • Should not be over-restrictive. • Should be based on the functionality of the candidate protocol, not on its structure. • Nice-to-haves: – Ability to define multiple tasks within a single framework. – Conceptual and technical simplicity.What do we want from a definition of security for a given task? • Should be mathematically rigorous (I.e., should be well-defined how a protocol is modeledand whether a given protocol is “in” or “out”). • Should provide an abstraction (“a primitive”) that matches our intuition for the requirements of the task. • Should capture “all realistic attacks” in the expected execution environment. • Should guarantee security when the primitive is needed elsewhere. • Should not be over-restrictive. • Should be based on the functionality of the candidate protocol, not on its structure. • Nice-to-haves: – Ability to define multiple tasks within a single framework. – Conceptual and technical simplicity.What do we want from a definition of security for a given task? • Should capture “all realistic attacks” in the expected execution environment. Issues include: – What are the network characteristics? (synchrony, reliability, etc.) – What are the capabilities of the attacker(s)? (controlling protocol participants? The communication links?In what ways? ) – What are the possible inputs? – What other protocols are running in the same system? • Should guarantee security when the primitive is needed elsewhere: – Take a protocol that assumes access to the “abstract primitive”, and let it work with a protocol that meets the definition. The overall behavior should remain unchanged.  Some flavor of “secure composability” is needed already in the basic desiderata.First candidate: The “classic” task of multiparty secure function evaluation • We have: – n parties, p1…pn, n>1, where each p has an input value x in D.i i Some of the parties may be corrupted. (Let’s restrict ourselves to static corruptions, for now.) – A probabilistic function f:Dn x R  Dn . – An underlying communication network • Want to design a “secure” protocol where each p has output i f(x1…xn,,r) .That is, want: i – Correctness: The honest parties get the correct function value of the parties’ inputs. – Secrecy: The corrupted parties learn nothing other than what is computable from their inputs and prescribed outputs.Examples: • F(x1 ,…,xn ) = x1 +…+xn • F(x1 ,…,xn ) = max(x1 +…+xn) • F(-,…,- ) = r U D • F((x0,x1),b)= (-,xb) (b in {0,1}) • FR((x,w),-) = (-,(x,R(x,w)) (R(x,w) is a binary relation) … • But, cannot capture “reactive” tasks (e.g., commitment, signatures, public-key encryption…)How to formalize? How to define correctness? Question: Based on what input values for the corrupted partiesshould the function be computed?(ie, recall: P should output f(x1…xn,,r) . But what should bei ithe x’s of the corrupted parties?) – If we require that f is computed on input values fixed from above then we get an unrealizable definition. – If we allow the corrupted parties to choose their inputs