Lecture Notes in Computer Science 2020 EditedbyG.Goos,J.HartmanisandJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Singapore Tokyo David Naccache (Ed.) Topics in Cryptology – CT-RSA 2001 The Cryptographers’ Track at RSA Conference 2001 San Francisco, CA, USA,April 8-12, 2001 Proceedings 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditor DavidNaccache GemplusCardInternational 34rueGuynemer,92447IssylesMoulineaux,France E-mail:[email protected]@compuserve.com Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Topicsincryptology:theCryptographers’TrackattheRSAconference 2001;proceedings/CT-RSA2001,SanFrancisco,CA,USA,April8- 12,2001.DavidNaccache(ed.).-Berlin;Heidelberg;NewYork; Barcelona;HongKong;London;Milan;Paris;Singapore;Tokyo: Springer,2001 (Lecturenotesincomputerscience;Vol.2020) ISBN3-540-41898-9 CRSubjectClassification (1998):E.3,G.2.1,D.4.6,K.6.5,F.2.1-2,C.2,J.1 ISSN0302-9743 ISBN3-540-41898-9Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specifically therightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilms orinanyotherway,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 SPIN:10782272 06/3142 543210 Preface You are holding the (cid:12)rst in a hopefully long and successful series of RSA Cryp- tographers’ Track proceedings. The Cryptographers’ Track (CT-RSA) is one of the many parallel tracks of the yearly RSA Conference. Other sessions deal with government projects, law and policy issues, freedom and privacy news, analysts’ opinions, standards, ASPs,biotechandhealthcare,(cid:12)nance,telecomandwirelesssecurity,developers, new products, implementers, threats, RSA products, VPNs, as well as crypto- graphy and enterprise tutorials. RSA Conference 2001 is expected to continue the tradition and remain the largest computer security event ever staged: 250 vendors, 10,000 visitors and 3,000 class-going attendees are expected in San Francisco next year. Iamverygratefultothe22membersoftheprogramcommitteefortheirhard work. The program committee received 65 submissions (one of which was later withdrawn)forwhichreviewwasconductedelectronically;almostallpapershad at least two reviews although most had three or more. Eventually, we accepted the 33 papers that appear in these proceedings. Revisions were not checked on their scienti(cid:12)c aspects and some authors will write (cid:12)nal versions of their papers for publication in refereed journals. As is usual, authors bear full scienti(cid:12)c and paternity responsibilities for the contents of their papers. The program committee is particularly indebted to 37 external experts who greatlyhelpedinthereviewprocess:Andr(cid:19)eAm(cid:18)egah,MihirBellare,CarineBour- sier, Fabienne Cathala, Jean-S(cid:19)ebastien Coron, Nora Dabbous, Jean-Franc(cid:24)ois Dhem, Serge Fehr, Gerhard Frey, Pierre Girard, Beno^(cid:16)t Gonzalvo, Shai Halevi, Helena Handschuh, Martin Hirt, Markus Jakobsson, Marc Joye, Neal Koblitz, Franc(cid:24)ois Koeune, Phil MacKenzie, Keith Martin, Alfred John Menezes, Victor Miller, Fabian Monrose, Mike Mosca, Pascal Paillier, Mireille Pauliac, B(cid:19)eatrice Peirani, David Pointcheval, Florence Qu(cid:18)es, Ludovic Rousseau, Doug Schales, Jean-Franc(cid:24)ois Schultz, Joseph Silverman, Christophe Tymen, Mathieu Vavas- sori, Yongge Wang and Robert Zuccherato. Special thanks are due to Julien Brouchierforskillfullymaintainingandupdatingtheprogramcommittee’sweb- site. It is our sincere hope that our e(cid:11)orts will contribute to reduce the distance between the academic community and the information security industry in the coming years. November 2000 David Naccache RSAConference2001isorganizedbyRSASecurityInc.anditspartnerorganizations aroundtheworld.TheCryptographers’TrackatRSAConference2001isorganizedby RSALaboratories(http://www.rsasecurity.com)andsponsoredbyCompaqCompu- ter Corporation, Hewlett-Packard, IBM, Intel Corporation, Microsoft, nCipher, EDS, RSA Security Inc., NIST and the National Security Agency. Program Committee David Naccache (Program Chair) .................................Gemplus, France Ross Anderson..............................Cambridge University, United Kingdom Josh Benaloh .............................................Microsoft Research, USA Daniel Bleichenbacher ........................Bell Labs, Lucent Technologies, USA Dan Boneh ...............................................Stanford University, USA Mike Burmester .......................Royal Holloway University, United Kingdom Don Coppersmith .............................................IBM Research, USA Rosario Gennaro ..............................................IBM Research, USA Ari Juels ..................................................RSA Laboratories, USA Burt Kaliski ...............................................RSA Laboratories, USA Kwangjo Kim ..................Information and Communications University, Korea (cid:26) Citibank, USA Arjen K. Lenstra ............... Technical University Eindhoven, The Netherlands Ueli Maurer ..............................................ETH Zurich, Switzerland Bart Preneel ..............................Katholieke Universiteit Leuven, Belgium Jean-Jacques Quisquater ................Universit(cid:19)e Catholique de Louvain, Belgium Michael Reiter ................................Bell Labs, Lucent Technologies, USA Victor Shoup ...........................................IBM Research, Switzerland Jacques Stern ....................................E(cid:19)cole Normale Sup(cid:19)erieure, France (cid:26) Certicom Research, Canada Scott Vanstone ................................... University of Waterloo, Canada Michael Wiener ......................................Entrust Technologies, Canada Moti Yung ............................................................Certco, USA Yuliang Zheng ........................................Monash University, Australia Phil Zimmerman ........................................................PGP, USA Table of Contents New Cryptosystems Faster Generation of NICE-Schnorr-Type Signatures ::::::::::::::::::: 1 Detlef Hu¨hnlein (secunet Security Networks AG) New Key Agreement Protocols in Braid Group Cryptography:::::::::::: 13 Iris Anshel (Arithmetica Inc.), Michael Anshel (City College of New York), Benji Fisher (Boston College), Dorian Goldfeld (Columbia University) RSA Improving SSL Handshake Performance via Batching ::::::::::::::::::: 28 Hovav Shacham (Stanford University), Dan Boneh (Stanford University) FromFixed-LengthMessagestoArbitrary-LengthMessagesPracticalRSA Signature Padding Schemes ::::::::::::::::::::::::::::::::::::::::: 44 Genevi(cid:18)eve Arboit (McGill University), Jean-Marc Robert (Gemplus Card International) AnAdvantageofLow-ExponentRSAwithModulusPrimesSharingLeast Signi(cid:12)cant Bits :::::::::::::::::::::::::::::::::::::::::::::::::::: 52 Ron Steinfeld (Monash University), Yuliang Zheng (Monash University) Symmetric Cryptography On the Strength of Simply-Iterated Feistel Ciphers with Whitening Keys:: 63 Paul Onions (Silicon Infusion Ltd.) Analysis of SHA-1 in Encryption Mode ::::::::::::::::::::::::::::::: 70 Helena Handschuh (Gemplus Card International), Lars R. Knudsen (University of Bergen), Matthew J. Robshaw (ISG, Royal Holloway) Fast Implementation and Fair Comparison of the Final Candidates for Advanced Encryption Standard Using Field Programmable Gate Arrays :: 84 Kris Gaj (George Mason University), Pawel Chodowiec (George Mason University) X Table of Contents Gambling and Lotteries Fair e-Lotteries and e-Casinos ::::::::::::::::::::::::::::::::::::::: 100 Eyal Kushilevitz (Department of Computer Science, Technion), Tal Rabin (IBM T.J. Watson Research Center) Secure Mobile Gambling :::::::::::::::::::::::::::::::::::::::::::: 110 Markus Jakobsson (Bell Laboratories, Lucent Technologies), David Pointcheval (ENS { CNRS), Adam Young (Lockheed Martin) Reductions, Constructions and Security Proofs Formal Security Proofs for a Signature Scheme with Partial Message Recovery:::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 126 Daniel R.L. Brown (Certicom Research), Don B. Johnson (Certicom Research) The Oracle Di(cid:14)e-Hellman Assumptions and an Analysis of DHIES::::::: 143 Michel Abdalla (Unversity of California, San Diego), Mihir Bellare (University of California, San Diego), Phillip Rogaway (University of California, Davis) REACT: Rapid Enhanced-Security Asymmetric Cryptosystem Transform : 159 Tatsuaki Okamoto (NTT Labs), David Pointcheval (ENS { CNRS) Flaws and Attacks Security Weaknesses in Bluetooth :::::::::::::::::::::::::::::::::::: 176 Markus Jakobsson (Bell Laboratories, Lucent Technologies), Susanne Wetzel (Bell Laboratories, Lucent Technologies) Distinguishing Exponent Digits by Observing Modular Subtractions :::::: 192 Colin D. Walter (Datacard platform7 seven, UMIST Manchester), Susan Thompson (Datacard platform7 seven) On the Power of Misbehaving Adversaries and Security Analysis of the Original EPOC :::::::::::::::::::::::::::::::::::::::::::::::::::: 208 Marc Joye (Gemplus Card International), Jean-Jacques Quisquater (UCL Crypto Group), Moti Yung (CertCo) Implementation Modular Exponentiation on Fine-Grained FPGA::::::::::::::::::::::: 223 Alexander Tiountchik (National Academy of Sciences of Belarus), Elena Trichina (PACT Informationstechnologie) Table of Contents XI ScalableAlgorithmforMontgomeryMultiplicationandItsImplementation on the Coarse-Grain Recon(cid:12)gurable Chip ::::::::::::::::::::::::::::: 235 Elena Trichina (PACT Informationstechnologie), Alexander Tiount- chik (National Academy of Sciences of Belarus) Software Implementation of the NIST Elliptic Curves Over Prime Fields :: 250 Michael Brown (University of Waterloo), Darrel Hankerson (Auburn University, Certicom Research), Julio Lo(cid:19)pez (University of Valle), Alfred Menezes (University of Waterloo, Certicom Research) Multivariate Cryptography The Security of Hidden Field Equations (HFE) :::::::::::::::::::::::: 266 Nicolas T. Courtois (Universit(cid:19)e de Toulon et du Var) QUARTZ, 128-Bit Long Digital Signatures:::::::::::::::::::::::::::: 282 Jacques Patarin (Bull CP8), Nicolas Courtois (Bull CP8), Louis Goubin (Bull CP8) FLASH, a Fast Multivariate Signature Algorithm :::::::::::::::::::::: 298 Jacques Patarin (Bull CP8), Nicolas Courtois (Bull CP8), Louis Goubin (Bull CP8) Number Theoretic Problems Analysis of the Weil Descent Attack of Gaudry, Hess and Smart ::::::::: 308 Alfred Menezes (University of Waterloo, Certicom Research), Minghua Qu (Certicom Research) Using Fewer Qubits in Shor’s Factorization Algorithm via Simultaneous Diophantine Approximation ::::::::::::::::::::::::::::::::::::::::: 319 Jean-Pierre Seifert (In(cid:12)neon Technologies) Passwords and Credentials Relying Party Credentials Framework :::::::::::::::::::::::::::::::: 328 Amir Herzberg (NewGenPay Inc.), Yosi Mass (IBM Haifa Research Lab) Password Authentication Using Multiple Servers ::::::::::::::::::::::: 344 David P. Jablon (Integrity Sciences, Inc.) More E(cid:14)cient Password-Authenticated Key Exchange :::::::::::::::::: 361 Philip MacKenzie (Bell Laboratories, Lucent Technologies) Protocols I Improved Boneh-Shaw Content Fingerprinting::::::::::::::::::::::::: 378 Yacov Yacobi (Microsoft Research)