Abstracts (Currently Available) for Workshop Talks %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: On the fundaments of secure multiparty protocols (talk series)" Speaker: Ran Canetti The goal of this talk series is to present and discuss the foundations of secure cryptographic protocols. I will first present definitions of protocol security, and show how protocols can be composed securely. Then I will use the above "framework" to take a fresh look at some basic general constructions of secure protocols. Naturally, this presentation will be tainted by my personal viewpoint. I hope it will stir up fruitful discussion. The series will consist of the following four parts. Each part may take anywhere from 0.5-2 hours, depending mainly on the audience interest. 1. Definitions of multiparty secure protocols. There have been several effors to come up with a set of definitions of security for multiparty secure protocols, most notably by Micali-Rogaway, Goldwasser-Levin, Beaver. I will concentrate on a definitional approach that I have been involved in. After presenting the general paradigm, I will describe definitions for several adversary models (passive, active, static, adaptive, information-theoretic, computational), and give hints on how this approach can be used to define security in other settings. Lastly I will shortly review other definitional approaches. 2. Composition of secure protocols. I will show how protocols can be composed in a way that maintains security. The composition method is the natural one, namely subroutine substitution (as defined by Micali and Rogaway). This will include formalizing the variants of the composition theorem for the above adversary models, sketching the proof(s), and then diving into the details until the audience cries for rescue. 3. Review the [BGW88] general construction of of secure protocols, for the information theoretic setting with adaptive adversaries. The presentation will be slightly different than the "standard" one, in that the security of each component in the construction will be first proven separately; then, the pieces will be put together, using the composition theorem, to establish the security of the overall protocol. Finally, the composition theorem will be used again to show that encrypting each message (using adaptively secure encryptions) results in secure protocols in the computational ("insecure channels") setting. 4. Review the [GMW87] general construction for the computational setting with static adversaries. Again, the various components are first presented and proven separately, and then the security of the overall protocol is established via the composition theorem. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: SECURE PROTOCOLS WITH INVISIBLE TRUSTED PARTIES Speaker: Silvio Micali Many crucial protocol problems (e.g., secret exchange, contract signing, and certified e-mail) involve a "symultaneous" exchange between just two parties, but cannot be cleanly solved by two-party protocols. Such protocol problems could often be solved with the help of a trusted third party, but this might generate congestions (in the network), liabilities (for the third party) and costs (to the users). We thus put forward and explore the power of an alternative model: two-party protocols with an INVISIBLE TRUSTED PARTY, that is, a party that does not participate in an ordinary execution, but, if something goes wrong, can still take a simple action to complete the execution properly. In particular, we show that Certified-E Mail possesses a clean and practical solution in this model. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Secure Multiparty Computation and Fault-Tolerant Quantum Computation. Speaker: Michael Ben Or Abstract: In this talk I shall explain the natural connection between these two "Fault-Tolerance" problems. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Multiuser Steganographic File Systems Speaker: Adi Shamir Abstract: In this talk we describe several implementations of steganographic file systems, which give users a very high level of protection against being compelled to disclose the contents of their secret files, even when the opponent has full access to the hardware and software of their computer, and can demand to see a plausible explanation for any suspicious looking file in their hard disk. We concentrate in particular on the harder case of multiuser systems, in which each party can manipulate its secret files in an arbitrary way without destroying the secret files of other users, even when he doen't know where they are stored or what is their contents. Joint work with Ross Anderson and Roger Needham. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Distributed KDC Speaker: Benny Pinkas. Network security is often based on trusted intermediaries. In fact, using such intermediaries seems inevitable for any large network. The use of public key operations typically relies on trusted Certificate Authorities (CAs), whereas networks whose security is only based on private key operations commonly use a Key Distribution Center (KDC). The use of a single trusted party (CA or KDC) introduces availability problems, whereas replicated copies of the trusted party are multiple points of failure for the system security. A much preferable approach which is captured in the notion of threshold cryptography is the distribution of trust among several parties. In this talk we consider the task of designing a distributed system of KDCs (DKDC) that answers both the availability and the security problems. Joint work with Moni Naor and Omer Reingold. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Applications of Crypto and Multi-Party Computations to E-Commerce Speaker: Amir Herzberg, The Internet offers direct, immediate connectivity among businesses and individuals globally - providing the potential for more efficient markets and processes. A major inhibitor is the lack of security, in particular, the danger that some parties will not perform their roles as promised. Of course, this scenario reminds us of multi-party computation models - or at least the motivation part of the Introductions. In fact, we believe cryptography and multi-party computation techniques could indeed be the key to enabling secure e-commerce solutions. In this brief informal presentation, we will mainly raise some questions and try to stimulate discussion. In particular: 1. What are the important E-commerce scenarios which need cryptographic solutions? 2. What additional analytical work is needed? (Answer: often we need more efficient solutions; sometimes, we may have to extend the foundations) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Span Programs with Multiplication Speaker: Ronald Cramer Monotone span programs (Karchmer and Wigderson), a linear algebra based model of computation, provide a powerful way of designing (linear) secret sharing schemes. We enhance this model to extend its usefulness into the domain of general multiparty computation secure against non-threshold adveraries: monotone span programs with multiplication. In this talk we introduce monotone span programs with multiplication, we completely classify which monotone Boolean functions are computable by them, and we give some upperbounds on their complexity in terms of certain monotone circuits. Finally, we show that for some concrete functions monotone span programs with multiplication are superpolynomially more efficient than monotone circuits. Joint work (see also Damgaard's abstract) with Ivan Damgaard and Ueli Maurer. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Trading Correctness for Privacy Speaker: Martin Hirt Abstract: This paper improves on the classical results in unconditionally secure multi-party computation among a set of $n$ players, by considering a model with three simultaneously occurring types of player corruption: the adversary can actively corrupt (i.e. take full control over) up to $t_a$ players, can passively corrupt (i.e. read the entire information of) up to $t_p$ additional players and, can fail-corrupt (i.e. stop the computation of) up to $t_f$ other players. The classical results are for the special cases of only passive ($t_a = t_f = 0$) or only active ($t_p = t_f = 0$) corruption. In the passive case, every function can be computed securely if and only if $t_p < n/2$. In the active case, every function can be computed securely if and only if $t_a < n/3$; when a broadcast channel is available, then this bound is $t_a < n/2$. These bounds are tight. Strictly improving these results, one of our results states that, in addition to tolerating $t_a