6 897 Advanced Topics in Cryptography Lecturers Ran Canetti Ron Rivest Focus 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 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 Potential encore On symbolic formal methods analysis of cryptographic protocols 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 modeled and 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 modeled and 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 pi has an input value xi in D 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 pi has output f x1 xn r i That is want 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 parties should the function be computed ie recall Pi should output f x1 xn r i But what should be the 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 then we run into problems Example Function f x1 x2 x1 x2 x1 x2 Protocol P1 sends x1 to P2 P2 sends x1 x2 back The protocol is both correct and secret But it s not secure Need an input independence property which blends secrecy and correctness How to formalize How to define secrecy An attempt It should be possible to generate the view of the corrupted parties given only their inputs and outputs Counter example Function F r U D Protocol P1 chooses r U D and sends r to P2 The protocol is clearly not secret P2 learns r Yet it is possible to generate P2 s view it s a random bit Need to consider the outputs of the corrupted parties together with the outputs of the uncorrupted parties