Secure Protocols for Complex Tasks in ComplexEnvironmentsAmit SahaiUniversity of California, Los [email protected] the last two decades, there has been tremendous success in placing cryptog-raphy on a sound theoretical foundation, and building an amazingly successfultheory out of it. The key elements in this Modern Cryptographic Theory arethe definitions capturing the intuitive, yet elusive notions of security in variouscryptographic settings. The definitions of the early 80’s proved to be extremelysuccessful in this regard. But with time, as the theory started addressing moreand more complex concerns, further notions of security had to be introduced.One of the most important concerns theory ventured into is of complex environ-ments where different parties are communicating with each other concurrentlyin many different protocols. A series of efforts in extending security definitionsled to the paradigm of Universally Composable (UC) Security [1], which alongwith modeling a general complex network of parties and providing definitionsof security in that framework, provided powerful tools for building protocolssatisfying such definitions.1The basic underlying notion of security in the UC framework and its manypredecessors is based on simulation. An “ideal” world is described, where allrequisite tasks get accomplished securely, as if by magic. The goal of the protocoldesigner is to find a way to accomplish these tasks in the “real” world, so that nomalicious adversary can take advantage of this substitution of ideal magic by realprotocols. To formalize this, we say that for every malicious adversary A thattries to take advantage of the real world, there is an adversary S that can achieveessentially the same results in the ideal world. The “results” are reflected in thebehavior of an environment. In this survey we shall refer to this notion of securityas “Environmental Security.” If a real-life protocol “Environmentally Securelyrealizes” a task, it ensures us that replacing the magic by reality does not openup new unforeseen threats to the system. (There may already be threats to thesystem even in the ideal world. But employing cryptographic primitives cannotoffer a solution if the ideal system itself is badly conceived.) The ideal-worldadversary S is called a simulator as it simulates the real-world behavior of A,inthe ideal world.A major advantage of Environmentally Secure (ES) protocols, as shown in[1], is that they are “Universally Composable,” i.e., roughly, if multiple copies1A similar framework to UC Security was independently proposed by Pfitzmann andWaidner [5, 6]. These two frameworks are conceptually very similar, although thereare a number of technical differences. We choose to concentrate on the UC frameworkin this survey.A. Canteaut and K. Viswanathan (Eds.): INDOCRYPT 2004, LNCS 3348, pp. 14–16, 2004.c Springer-Verlag Berlin Heidelberg 2004Secure Protocols for Complex Tasks in Complex Environments 15of an ES-protocol are present in the system (in fact they could be copies ofdifferent protocols), then they collectively ES-realize the collection of the tasksthey individually ES-realize. Hence we shall often refer to the framework in [1]as the ES/UC framework, or simply ES-framework or UC-framework.Unfortunately, this notion of security turns out to be too strong to be achiev-able in standard settings. It has been shown that much of the interesting crypto-graphic tasks (including e.g. commitment, zero knowledge and secure multi-partycomputation) cannot be ES-realized when the adversary can control at least halfthe parties [1, 2, 3]. On the other hand, under a trusted set-up assumption –that there is a public reference string chosen by a completely trusted party – itis known how to build protocols for the most ambitious of cryptographic tasks(general secure multiparty computation with dishonest majority) satisfying theEnvironmental Security definition [4]. However, if no trusted party is assumed,then we are left with the strong impossibility results mentioned above.We recently overcame these impossibility results in [7]. In that work, wedevelop secure protocols in the plain model (without any trusted set-up assump-tions), by modifying the notion of security, while still retaining the composability.The new direction taken by this work opens up many interesting new questionsand directions for the field of cryptographic protocols.In this survey talk, we will outline the fundamental ideas and results leadingup to the recent work mentioned above, and the many open questions thatremain.Acknowledgements. The author’s research in this area has been supported bygenerous grants from the NSF ITR and Cybertrust programs, as well as anAlfred P. Sloan Foundation Research Fellowship.References1. Ran Canetti. Universally composable security: A new paradigm for cryptographicprotocols. Electronic Colloquium on Computational Complexity (ECCC) (016):(2001) (Preliminary version in IEEE Symposium on Foundations of Computer Sci-ence, pages 136–145, 2001.)2. Ran Canetti and Marc Fischlin. Universally composable commitments. InCRYPTO, pages 19–40, 2001.3. R. Canetti, E. Kushilevitz, and Y. Lindell. On the limitations of universally compos-able two-party computation without set-up assumptions. In EUROCRYPT, pages68–86, 2003.4. R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai. Universally composable two-party and multi-party secure computation. In ACM Symposium on Theory of Com-puting, pages 494–503, 2002.5. B. Pfitzmann and M. Waidner. Composition and integrity preservation of securereactive systems. In ACM Conference on Computer and Communications Security(CCS 2000), pp. 245–254, 2000.16 A. Sahai6. B. Pfitzmann and M. Waidner. A Model for Asynchronous Reactive Systems andits Application to Secure Message Transmission. In IEEE Symposium on Securityand Privacy, 2001.7. Manoj Prabhakaran and Amit Sahai. New Notions of Security: Achieving UniversalComposability without Trusted Setup. In ACM Symposium on Theory of Com-puting, 2004. Full version to appear in SIAM Journal of Computing, Special Issuefor STOC 2004. Preliminary full version available at the Cryptology ePrint