6.897: Selected Topics in Cryptography Lectures 9 and 10 Lecturer: Ran CanettiHighlights of past lectures Presented two frameworks for analyzing protocols: • A basic framework: – Only function evaluation – Synchronous – Non-adaptive corruptions – Modular composition (only non-concurrent) • A stronger framework (UC): – General reactive tasks – Asynchronous (can express different types of synchrony) – Adaptive corruptions – Concurrent modular composition (universal composition)P1 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:Lectures 9 and 10 UC Commitment and Zero-Knowledge • Quick review of known feasibility results in the UC framework. • UC commitments: The basic functionality, Fcom. • Impossiblity of realizing Fcom in the plain model. • Realizing Fcom in the common reference string model. • Multiple commitments with a single string: – Functionality Fmcom. – Realizing Fmcom. • From UC commitments to UC ZK: Realizing Fzk in the Fcom-hybrid model.do zcyk02]Questions: • How to write ideal functionalities that adequately capture known/new tasks? • Are known protocols UC-secure? (Do these protocols realize the ideal functionalities associated with the corresponding tasks?) • How to design UC-secure protocols?Existence results: Honest majority Multiparty protocols with honest majority: Thm: Can realize any functionality [C. 01]. (e.g. use the protocols of [BenOr-Goldwasser-Wigderson88, Rabin-BenOr89,Canetti-Feige-Goldreich-Naor96]).Two-party functionalities • Known protocols do not work.(“black-box simulation with rewinding” cannot be used). • Many interesting functionalities (commitment, ZK, coin tossing, etc.) cannot be realized in plain model. • In the “common random string model” can do: – UC Commitment [Canetti-Fischlin01,Canetti-Lindell-Ostrovsky-Sahai02,Damgard-Nielsen02, Damgard-Groth03,Hofheinz-QuedeMueler04]. – UC Zero-Knowledge [CF01, DeSantis et.al. 01] – Any two-party functionality [CLOS02,Cramer-Damgard-Nielsen03] (Generalizes to any multiparty functionality with anynumber of faults.)UC Encryption and signature • Can write a “digital signature functionality” Fsig. Realizing Fsigis equivalent to “security against chosen message attacks”as in [Goldwasser-Micali-Rivest88]. – Using Fsig, can realize “ideal certification authorities” and “ideally authenticated communication”. • Can write a “public key encryption functionality”, Fpke. Realizing Fpke w.r.t. non-adaptive adversaries is equivalent to “security against chosen ciphertext attacks (CCA)” as in [Rackoff-Simon91,Dolev-Dwork-Naor91,…]. – Can formulate a relaxed variant of Fpke, that still captures most of the current applications of CCA security. – What about realizing Fpke w.r.t. adaptive adversaries? • As is, it’s impossible. • Can relax Fpke a bit so that it becomes possible (but still verycomplicated) [Canetti-Halevi-Katz04]. How to do it simply?UC key-exchange and secure channels • Can write ideal functionalities that capture Key-Exchange and Secure-Channels. • Can show that natural and practical protocols are secure: ISO 9798-3, IKEv1, IKEv2, SSL/TLS,… • What about password-based key exchange? • What about modeling symmetric encryption and message authentication as ideal functionalities?UC commitmentsThe commitment functionality, Fcom 1. Upon receiving (sid,C,V,“commit”,x) from(sid,C), do: 1. Record x 2. Output (sid,C,V, “receipt”) to (sid,V) 3. Send (sid,C,V, “receipt”) to S 2. Upon receiving (sid,“open”) from (sid,C), do: 1. Output (sid,x) to (sid,V) 2. Send (sid,x) to S 3. Halt. Note: Each copy of Fcom is used for a single commitment/decommitment Only. Multiple commitments require multiple copies of Fcom.Impossibility of realizing Fcom in the plain model can be realized:Fcom – By a “trivial” protocol that never generates any output. (The simulator never lets Fcom to send output to any party.) – By a protocol that uses third parties as “helpers”.  A protocol is: – Terminating, if when run between two honest parties, some output is generated by at least one party. – Bilateral, if only two parties participate in it. Theorem: There exist no terminating, bilateral protocols that securely realize Fcom in the plain real-life model. (Theorem holds even in the Fauth-hybrid model.)Proof Idea: Let P be a protocol that realizes Fcom in the plain model, and let S be an ideal-process adversary for P, for the case that the commiter is corrupted. Recall that S has to explicitly give the committed bit to Fcom before the opening phase begins. This means that S must be able to somehow “extract” the committed value b from the corrupted committer. However, in the UC framework S has no advantage over a real-life verifier. Thus, a corrupted verifier can essentialy run S and extract the committed bit b from an honest committer, before the opening phase begins, in contradiction to the secrecy of the commitment.More precisely, we proceed in two steps: (I) Consider the following environment Zc and real-life adversary Ac that controls the committer C: –Ac is the dummy adversary: It reports to Zc any message received from the verifier V, and sends to V any message provided by Zc. –Zc chooses a random bit b, and runs the code of the honest C by instructing Ac to deliver all the messages sent by C. Once V outputs “receipt”, Zc runs the opening protocol of C with V, and outputs 1 if the output bit b’ generated by V is equal to b. From the security of P there exists an ideal-process adversary Sc such that IDEALFcomSc,,Zc ~ EXECP,Ac,Zc. But: – In the real-life mode, b’, the output of V, is almost always the same as the bit b that secretly Z chose. – Consequently, also in the ideal process, b’=b almost always. – Thus, the bit b’’ that S provides Fcom at the commitment phase is almost always equal to b.(II) Consider the following environment Zv and real-life adversary Av that controls the verifier V: –Zv chooses a random bit b, gives b as input to the honest commiter, and outputs 1 if the adversary output a bit b’=b. –Av runs Sc. Any message received from C is