Lecture Notes in Computer Science 2139 EditedbyG.Goos,J.Hartmanis,andJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Singapore Tokyo Joe Kilian (Ed.) Advances in Cryptology – CRYPTO 2001 21stAnnual International Cryptology Conference, Santa Barbara, California, USA,August 19-23, 2001 Proceedings 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditor JoeKilian YianilosLabs. 707StateRd.,Rt.206,Suite212 Princeton,NJ08540,USA E-mail:[email protected] Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Advancesincryptology:proceedings/CRYPTO2001,21stAnnual InternationalCryptologyConference,SantaBarbara,California,USA,August 19-23,2001.JoeKilian(ed.).[IACR].-Berlin;Heidelberg;NewYork; Barcelona;HongKong;London;Milan;Paris;Singapore;Tokyo: Springer,2001 (Lecturenotesincomputerscience;Vol.2139) ISBN3-540-42456-3 CRSubjectClassification(1998):E.3,G.2.1,F.2.1-2,D.4.6,K.6.5,C.2,J.1 ISSN0302-9743 ISBN3-540-42456-3Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. Springer-VerlagBerlinHeidelbergNewYork amemberofBertelsmannSpringerScience+BusinessMediaGmbH http://www.springer.de ©Springer-VerlagBerlinHeidelberg2001 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyPTP-Berlin,StefanSossna Printedonacid-freepaper SPIN10840151 06/3142 543210 Preface Crypto 2001, the 21st Annual Crypto conference, was sponsored by the Inter- national Association for Cryptologic Research (IACR) in cooperation with the IEEE Computer Society Technical Committee on Security and Privacy and the ComputerScienceDepartmentoftheUniversityofCaliforniaatSantaBarbara. The conference received 156 submissions, of which the program committee selected34forpresentation;onewaslaterwithdrawn.Theseproceedingscontain therevisedversionsofthe33submissionsthatwerepresentedattheconference. These revisions have not been checked for correctness, and the authors bear full responsibility for the contents of their papers. The conference program included two invited lectures. Mark Sherwin spoke on, \Quantum information processing in semiconductors: an experimentalist’s view." Daniel Weitzner spoke on, \Privacy, Authentication & Identity: A recent history of cryptographic struggles for freedom." The conference program also included its perennial \rump session," chaired by Stuart Haber, featuring short, informal talks on late{breaking research news. As I try to account for the hours of my life that flew o(cid:11) to oblivion, I realize that most of my time was spent cajoling talented innocents into spending even moretimeonmybehalf.IhaveaccumulatedmoredebtsthanIcaneverhopeto repay. As mere statements of thanks are certainly insu(cid:14)cient, consider the rest of this preface my version of Chapter 11. I would like to (cid:12)rst thank the many researchers from all over the world who submitted their work to this conference. Without them, Crypto is just a pile of shrimp and chocolate covered strawberries. IthankDavidBalenson,thegeneralchair,forshieldingmefrominnumerable logistical headaches, and showing great generosity in supporting my e(cid:11)orts. Selecting from so many submissions is a daunting task. My deepest thanks go to the members of the program committee, for their knowledge, wisdom, and near-masochistic work ethic. We in turn have relied heavily on the expertise of the many outside reviewers who assisted us in our deliberations. My thanks to all those listed on the following pages, and my thanks and apologies to any I have missed. I thank Rebecca Wright for hosting the program committee meeting in New York City, AT&T for providing the space, and Sandy Barbu for helping out with the local arrangements. Thanks also go to Ran Canetti, my favorite native culinary guide, wherever I go, for organizing the post{deliberations dinner. I thank the people who, by their past and continuing work, have greatly streamlined the submission and review process. All but one of the submissions were handled using Chanathip Namprempre’s web-based submission software. Reviews were administered using software written by Wim Moreau and Joris Claessens, developed under the guidance of Bart Preneel. These software packa- geshavemadetheprocessidiotproof,andnearlytheorist-proof.Mythanksalso go to Sam Rebelsky for writing the email-based predecessor of the submission VI Preface software. He and the other members of the SIGACT Electronic Publications Board have for many years made program committee chairs’ lives much more bearable. IamgratefultoMihirBellare,lastyear’sprogramchair,andKevinMcCurley and Josh Benaloh, my main contacts with the IACR board, for patiently trying to teach me my job. EvenifIcan’treallyaccountforwhatI,personally,wasdoing,thehoursdid go somewhere. I thank my boss, Peter Yianilos, for being so supportive of my e(cid:11)orts, and so absurdly forgiving of the time it has taken away from my work. Last,andmoreimportantly,I’dliketothankmyfamily,Dina,Gersh,andPearl, for their support, understanding, and love. June 2001 Joe Kilian CRYPTO 2001 August 19{23, 2001, Santa Barbara, California, USA Sponsored by the International Association for Cryptologic Research (IACR) in cooperation with IEEE Computer Society Technical Committee on Security and Privacy, Computer Science Department, University of California, Santa Barbara General Chair David Balenson, NAI Labs, Network Associates, Inc., USA Program Chair Joe Kilian, Yianilos Labs, USA Program Committee Bill Aiello..............................................AT&T Research, USA Don Beaver......................................................CertCo, USA Josh Benaloh........................................Microsoft Research, USA Antoon Bosselaers....................Katholieke Universiteit Leuven, Belgium Jan Camenisch.......................................IBM Zurich, Switzerland Ran Canetti..........................................IBM T. J. Watson, USA Claude Cr(cid:19)epeau....................................McGill University, Canada Alfredo De Santis..................................Universita(cid:18) di Salerno, Italy Marc Girault..........................................France Telecom, France Stuart Haber......................................InterTrust STAR Lab, USA Tatsuaki Okamoto..........................................NTT Labs, Japan Jacques Patarin................................................BULL, France Erez Petrank..................................................Technion, Israel Omer Reingold.........................................AT&T Research, USA Kazue Sako............................NEC C&C Media Research Lab, Japan Tomas Sander.....................................InterTrust STAR Lab, USA Doug Stinson.................................University of Waterloo, Canada Yacov Yacobi........................................Microsoft Research, USA Advisory Members Mihir Bellare (Crypto 2000 program chair).......................UCSD, USA Moti Yung (Crypto 2002 program chair).........................CertCo, USA VIII External Reviewers Table of Contents Foundations On the (Im)possibility of Obfuscating Programs.......................... 1 Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang Universally Composable Commitments.................................... 19 Ran Canetti and Marc Fischlin Traitor Tracing Revocation and Tracing Schemes for Stateless Receivers................... 41 Dalit Naor, Moni Naor, and Je(cid:11) Lotspiech Self Protecting Pirates and Black-Box Traitor Tracing.................... 63 Aggelos Kiayias and Moti Yung Multi-party Computation Minimal Complete Primitives for Secure Multi-party Computation........ 80 Matthias Fitzi, Juan A. Garay, Ueli Maurer, and Rafail Ostrovsky Robustness for Free in Unconditional Multi-party Computation........... 101 Martin Hirt and Ueli Maurer Secure Distributed Linear Algebra in a Constant Number of Rounds...... 119 Ronald Cramer and Ivan Damg(cid:23)ard Two-Party Computation Two-Party Generation of DSA Signatures................................. 137 Philip Mackenzie and Michael K. Reiter Oblivious Transfer in the Bounded Storage Model......................... 155 Yan Zong Ding Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation............................................................. 171 Yehuda Lindell Elliptic Curves Faster Point Multiplication on Elliptic Curves with E(cid:14)cient Endomorphisms.......................................................... 190 Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone On the Unpredictability of Bits of the Elliptic Curve Di(cid:14)e{Hellman Scheme................................................................... 201 Dan Boneh and Igor E. Shparlinski