The Weizmann Institute of Science Faculty of Mathematics and Computer Science Walmart Lecture Series in Cryptography and Complexity Seminar Room, Room 261, Ziskind Building on Thursday, June 16, 2011 at 14:30 Amit Sahai University of California, Los Angeles will speak on A New Protocol Compiler Abstract: One of the most fundamental goals in cryptography is to design protocols that remain secure when adversarial participants can engage in arbitrary malicious behavior. In 1986, Goldreich, Micali, and Wigderson presented a powerful paradigm for designing such protocols: their approach reduced the task of designing secure protocols to designing protocols that only guarantee security against ``honest-but-curious" participants. By making use of zero-knowledge proofs, the GMW paradigm enforces honest behavior without compromising secrecy. Over the past two decades, this approach has been the dominant paradigm for cryptographic protocol design. In this talk, we present a new general paradigm / protocol compiler for secure protocol design. Our approach also reduces the task of designing secure protocols to designing protocols that only guarantee security against honest-but-curious participants. However, our approach avoids the use of zero-knowledge proofs, and instead makes use of multi-party protocols in a much simpler setting - where the majority of participants are completely honest (such multi-party protocols can exist without requiring any computational assumptions). Our paradigm yields protocols that rely on Oblivious Transfer (OT) as a building block. This offers a number of advantages in generality and efficiency. In contrast to the GMW paradigm, by avoiding the use of zero-knowledge proofs, our paradigm is able to treat all of its building blocks as ``black boxes". This allows us to improve over previous results in the area of secure computation. In particular, we obtain: * Conceptually simpler and more efficient ways for basing unconditionally secure cryptography on OT. * More efficient protocols for generating a large number of OTs using a small number of OTs. * Secure and efficient protocols which only make a black-box use of cryptographic primitives or underlying algebraic structures in settings where no such protocols were known before. This talk is based primarily on joint works with Yuval Ishai (Technion) and Manoj Prabhakaran (UIUC).