6.897: Selected Topics in Cryptography Lectures 13 and 14Highlights of last week’s lecturesThis week:PowerPoint PresentationSlide 5A more abstract viewA formalizationExample: FmcomExample: FFcrs (with distribution D)The composition operation: Universal Composition with Joint State (JUC)Slide 11Application of the JUC theorem to the construction of [CLOS]Slide 13Slide 14Slide 15How about general protocols in the CRS model?Application of the JUC theorem to signature-based protocolsDigital signatures as an ideal functionalityThe deal signature functionality: Attempt 1The ideal signature functionality: Attempt 2The ideal signature functionality: Attempt 3The ideal signature functionality: Attempt 4The ideal signature functionality: FsigThe privacy-preserving ideal signature functionality: Fpriv-sigSlide 25Slide 26Slide 27Slide 28Slide 29Authenticated communication using FsigThe “public registry” functionality, FregThe certification functionality: FcertRealizing Fcert in the (Freg,Fsig)-hybrid modelReminder: The authenticated message transmission functionality, FauthRealizing Fauth in the Fcert-hybrid modelAuthenticating multiple messages with a single verification keyThe multi-session certification functionality: FFcertRealizing FFcert using a single copy of Fcert6.897: Selected Topics in CryptographyLectures 13 and 14Lecturers: Ran Canetti, Ron RivestScribes?Highlights of last week’s lectures• S howed how to realize Fzk in the Fcom-hybrid model.• S howed how to realize any “standard” functionality:–In the Fauth-hybrid model, for semi-honest adversaries. –in the (Fauth,Fcrs)-model, for Byzantine adversaries.–In the Fauth-hybrid model, for Byzantine adversaries with honest majority. •This week:•Universal com posit ion wi th joi nt st ate: mo tivatio n, formula tion , proof, uses. •UC formul ation of sig nature s che mes:–The si gnatu re functi onali ty, Fsig.–Equival ence wit h CMA-sec urity •Achi eving au thentic ated commu nica tion: Realizi ng Fauth given Fsig and ce rtific ation a uthoriti es.•Yoav (after last lectu re): “Gosh, we would need a really lo ng referen ce st ring to rea lize fun ction ali ties t his wa y…”Indeed, a naïve use o f the CRS woul d mean:–A copy of Fcrs per copy of Fcom.–O(k) copies of Fcom per co py of Fzk.–O(r) copies of Fzk per copy of Fcp to com pile a p rotocol with r rounds.–O(n) co pies of Fcp in a protocol for n parti es…•Is it really necessary to use so many copies of the CRS?First answer: We can realize all the commitments using a single copy of Fmcom, which in turn uses a single copy of Fcrs. But, if we do that then we need to analyze the entire multiparty protocol (including all copies of Fzk, Fcp, etc.) as a single unit. This does away with much of the benefits of the UC theorem... In fact, this is not specific to the UC framework: whenever we analyze multiple protocols that have a common subroutine, we analyze them in one piece. (Examples: multiple copies of NIZK over a single CRS, or multiple key exchange sessions using a single long-term authentication module [BR93])Can we do better?Can we continue writing and analyzing single-instance functionalities, and still have them use some joint state and randomness?A more abstract viewWe have:•A protocol Q in the F-hybrid model for some F, that uses multiple independent copies of F. (e.g., F is Fcom, and Q is the Blum ZK protocol, or multiple copies of it.)•A protocol P that realizes (in one instance) multiple independent copies of F. (e.g., P is the protocol that realizes Fmcom.)Can we compose them while maintaining security?A formalization•Multi-instance extensions of ideal functionalities: Let F be an ideal functionality. Then the multi-session extension of F, denoted FF, proceeds as follows: - FF runs multiple copies of F. Each copy has its own identifier, denoted ssid. - FF expects all its inputs to be of the form (sid,ssid,…), where sid is the session id of FF, and ssid is an identifier for the copy of F run within FF. An incoming message with ssid s is then forwarded to the copy of F with ssid s. If no such copy exist, then a new one is invoked and is given ssid s. - Whenever a copy ssid of F within FF wishes to generate output to some party, or send a message to the adversary, then FF prepends its sid to the message and forwards it to the said recipient.Example: FmcomFmcom is the multi-session extension of Fcom (ie, Fmcom=FFcom).1. Upon receiving (sid,cid,C,V,“commit”,x) from (sid,C), do:1. Record (cid,x) 2. Output (sid,cid,C,V, “receipt”) to (sid,V)3. Send (sid,cid,C,V, “receipt”) to S2. Upon receiving (sid,cid“open”) from (sid,C), do:1. Output (sid,cid,x) to (sid,V)2. Send (sid,cid,x) to SExample: FFcrs (with distribution D)1. Upon receiving (sid,ssid,pid,“crs”) from (sid,pid), do:1. If there is a recorded pair (ssid,v) then output v to (sid,pid) and send (ssid,pid,v) to the adversary.2. Else, choose a value v from D, record (ssid,v), and continue as in Step 1.1.The composition operation:Universal Composition with Joint State (JUC)Start with:•A protocol Q in the F-hybrid model (that may run multiple copies of F).•A protocol P that securely realizes FF.Construct the composed protocol Q[P]:•At the first activation of Q[P], each party invokes a copy of P with some fixed sid (say, sid=0).•Whenever protocol Q calls a copy of F with input (sid=s,x), Q[P] calls P with input (sid=0,ssid=s,x). •Each output (0,s,y) of P is treated as an output (s,y) coming from the copy of F with sid=s.Theorem [JUC: UC with joint state]:Let Q be a protocol in the F-hybrid model, and let P be a protocol that securely realizes FF. Then protocol Q[P] emulates protocol Q. That is: for any adversary A there exists an adversary H such that for any environment Z we have: EXECFQ,H,Z ~ EXECQ[P],A,Z .Corollary:If Q securely realizes some ideal functionality G then so does protocol Q[P].Application of the JUC theorem to the construction of [CLOS]Here F is Fcom and FF is Fmcom:•Can write and realize each functionality (ZK,C&P,general compiler) for a single instance. •Can use the UC theorem to obtain a composed protocol Q in the Fcom–hybrid model. Protocol Q uses many copies of Fcom.•Can then use the JUC theorem to compose Q with a single copy of the protocol that realizes Fmcom, thus using only a single copy of the CRS.Proof of the JUC theorem:Plan:Define a protocol Q’ in the