Lecture Notes in Computer Science 1751 Editedby G.Goos,J. Hartmanis,and J.vanLeeuwen Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Singapore Tokyo Hideki Imai Yuliang Zheng (Eds.) Public Key Cryptography Third International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000 Melbourne, Victoria, Australia, January 18-20, 2000 Proceedings SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditors HidekiImai UniversityofTokyo,InstituteofIndustrialScience,TheThirdDepartment 7-22-1,Roppongi,Minato-ku,Tokyo,106-8558,Japan E-mail:[email protected] YuliangZheng MonashUniversity,SchoolofComputingandInformationTechnology McMahonsRoad,Frankston,Melbourne,VIC3199,Australia E-mail:[email protected] Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Publickeycryptography:proceedings/ThirdInternationalWorkshopon PracticeandTheoryinPublicKeyCryptosystems,PKC2000,Melbourne, Victoria,Australia,January18-20,2000.HidekiImai;YuliangZheng(ed.). -Berlin;Heidelberg;NewYork;Barcelona;HongKong;London; Milan;Paris;Singapore;Tokyo:Springer,2000 (Lecturenotesincomputerscience;Vol.1751) ISBN3-540-66967-1 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-66967-1Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. (cid:2)c Springer-VerlagBerlinHeidelberg2000 PrintedinGermany Typesetting:Camera-readybyauthor SPIN:10719554 06/3142–543210 Printedonacid-freepaper Preface ThePKC2000conferencewasheldattheMelbourneExhibitionCentre,Victoria, Australia, January 18-20, 2000. It was the third conference in the international workshop series dedicated to practice and theory in public key cryptography. The program committee of the conference received 70 full submissions from around the world, of which 31 were selected for presentation. All submissions were reviewed by experts in the relevant areas. The programcommittee consisted of 19 experts in cryptographyand data secu- rity drawn from the international research community, these being Chin-Chen Chang (National Chung Cheng University, Taiwan), Claude Cr´epeau (McGill University, Canada), Ed Dawson (Queensland University of Technology, Aus- tralia), Yvo Desmedt (Florida State University, USA), Hideki Imai (Co-chair, UniversityofTokyo,Japan),MarkusJakobsson(BellLabs,USA),KwangjoKim (InformationandCommunicationsUniversity,Korea),ArjenLenstra(Citibank, USA),TsutomuMatsumoto(YokohamaNationalUniversity,Japan),DavidNac- cache (Gemplus, France), Eiji Okamoto (University of Wisconsin-Milwaukee, USA),TatsuakiOkamoto(NTTLabs,Japan),JosefPieprzyk(UniversityofWol- longong, Australia), Jean-Jacques Quisquater (Universit´e Catholique de Lou- vain, Belgium), Nigel Smart (HP Labs Bristol, UK), Vijay Varadharajan (Uni- versity of Western Sydney, Australia), Serge Vaudenay (Ecole Polytechnique F´ed´erale de Lausanne, Switzerland), Moti Yung (CertCo, USA), and Yuliang Zheng (Co-chair, Monash University, Australia). Members of the committee spent numerous hours in reviewing the submissions and providing advice and comments on the selection of papers. The program committee also asked expert advice of many of their colleagues, including: MasayukiAbe, KazumaroAoki,PaulAshley, JoonsangBaek,Olivier Baudron, Christophe Bidan, Dan Boneh, Colin Boyd, Chris Charnes, Jean- S´ebastien Coron, Ed Dawson, Paul Dumais, Kenneth Finlayson, Pierre-Alain Fouque, Atsushi Fujioka, Chandana Gamage, Juan Garay, Hossein Ghodosi, Pierre Girard, Jean-Luc Giraud, Louis Granboulan, Marc Gysin, Stuart Haber, Helena Handschuh, Ari Juels, Tetsutaro Kobayashi, Byongcheon Lee, Wei-Bin Lee, Phil MacKenzie, Wenbo Mao, William Millan, David M’Ra¨ıhi, Yi Mu, Shinichi Nakahara, Kenny Nguyen, Phong Nguyen, David Pointcheval, Pascal Paillier, Ludovic Rousseau, Selwyn Russell, David Soldera, Stuart Stubblebine, KoutarouSuzuki,ChristopheTymen,ShigenoriUchiyama,SusanneWetzel,Ste- fan Wolf, and Chuan-Kun Wu. We would like to take this opportunity to thank all the program committee membersandexternalexpertsfortheirinvaluablehelpinproducingsuchahigh quality program. We are especially indebted to Chin-Chen Chang who made sure all the submissions assigned to him were properly reviewed in spite of the devastating earthquake and its countless aftershocks that rockedTaiwanin late September 1999. VI Preface The conference would not have been successful without the financial support from both Imai Laboratory (imailab-www.iis.u-tokyo.ac.jp) of the Institute of Industrial Science, University of Tokyo, and LINKS – Laboratory for Infor- mation and Network Security (www.pscit.monash.edu.au/links/) of the Faculty of Information Technology, Monash University. Our appreciation also goes to members ofLINKS, including JeraldChong, Chandana Gamage,Lionnel Heng, Khaled Khan, Jussi Leiwo, Patrik Mihailescu, and E-Yang Tang for their skill- ful and professionalassistancein organizingthis conference.Chandana Gamage deserves special thanks for helping out during the entire refereeing and editing process. Last, but not least, we would like to thank all the authors who submitted their paperstotheconference(includingthosewhosesubmissionswerenotsuccessful), as well as the conference participants from around the world, for their support which made this conference possible. January 2000 Hideki Imai Yuliang Zheng PKC2000 2000 International Workshop on Practice and Theory in Public Key Cryptography Melbourne Exhibition Centre, Australia January 18-20, 2000 Sponsored by Imai Laboratory of the Institute of Industrial Science, University of Tokyo, Japan (imailab-www.iis.u-tokyo.ac.jp) and LINKS – Laboratory for Information and Network Security of Monash University, Australia (www.pscit.monash.edu.au/links/) Program Committee Hideki Imai, Co-chair (University of Tokyo, Japan) Yuliang Zheng, Co-chair (Monash University, Australia) Chin-Chen Chang (National Chung Cheng University, Taiwan) Claude Crepeau (McGill University, Canada) Ed Dawson (Queensland University of Technology, Australia) Yvo Desmedt (Florida State University, USA) Markus Jakobsson (Bell Labs, USA) Kwangjo Kim (Information and Communications University, Korea) Arjen Lenstra (Citibank, USA) Tsutomu Matsumoto (Yokohama National University, Japan) David Naccache (Gemplus, France) Eiji Okamoto (University of Wisconsin-Milwaukee, USA) Tatsuaki Okamoto (NTT Labs, Japan) Josef Pieprzyk (University of Wollongong, Australia) Jean-Jacques Quisquater (Universit´e Catholique de Louvain, Belgium) Nigel Smart (HP Labs Bristol, UK) Vijay Varadharajan (University of Western Sydney, Australia) Serge Vaudenay (EPFL, Switzerland) Moti Yung (CertCo, USA) Contents A Practical and Secure Fault-Tolerant Conference-Key Agreement Protocol .........................................................1 Wen-Guey Tzeng (Nat Chiao Tung Uni, Taiwan) An Efficient NICE-Schnorr-Type Signature Scheme ........................14 Detlef Hu¨hnlein, and Johannes Merkle (secunet, Germany) Identification of Bad Signatures in Batches .................................28 Jarosl(cid:2)aw Pastuszak, Dariusz Micha(cid:2)lek (Polish Acad of Sci, Poland), Josef Pieprzyk, and Jennifer Seberry (Uni of Wollongong, Australia) Some Remarks on a Fair Exchange Protocol ...............................46 Jianying Zhou, Robert Deng, and Feng Bao (Kent Ridge Digital Labs, Singapore) Gaudry’s Variant against C Curves ......................................58 ab Seigo Arita (NEC, Japan) An Identification Scheme Based on Sparse Polynomials .....................68 William D. Banks, Daniel Lieman (Uni of Missouri, USA), and Igor E. Shparlinski (Macquarie Uni, Australia) A State-Based Model for Certificate Management Systems .................75 Chuchang Liu, Maris A. Ozols, Marie Henderson, and Tony Cant (DSTO, Australia) Confidence Valuation in a Public-Key Infrastructure Based on Uncertain Evidence ..............................................93 Reto Kohlas, and Ueli Maurer (ETH, Switzerland) The Composite Discrete Logarithm and Secure Authentication ............113 David Pointcheval (ENS, France) Chosen-Ciphertext Security for Any One-Way Cryptosystem ..............129 David Pointcheval (ENS, France) Short Proofs of Knowledge for Factoring ..................................147 Guillaume Poupard, and Jacques Stern (ENS, France) Secure and Practical Tree-Structure Signature Schemes Based on Discrete Logarithms ............................................167 X.Y.Wang (Uni of Hong Kong, and Shandong Uni, China), L.C.Hui, K.P.Chow, W.W.Tsang, C.F.Chong, and H.W.Chan (Uni of Hong Kong, China) X Contents All-or-Nothing Transform and Remotely Keyed Encryption Protocols .....178 Sang Uk Shin, Weon Shin, and Kyung Hyune Rhee (PuKyong Nat Uni, Korea) Security of Public Key Certificate Based Authentication Protocols ........196 Wu Wen, Takamichi Saito, and Fumio Mizoguchi (Sci Uni of Tokyo, Japan) Efficient Implementation of Schoof’s Algorithm in Case of Characteristic 2 ................................................210 TetsuyaIzu,JunKogure,andKazuhiro Yokoyama (FujitsuLabs,Japan) Key Recovery in Third Generation Wireless Communication Systems .....223 Juanma Gonz´alez Nieto (QUT, Australia), DongGook Park (QUT, Australia, and Korea Telecom), Colin Boyd, and Ed Dawson (QUT, Australia) Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications ....................................238 Katsuyuki Okeya, Hiroyuki Kurumatani (Hitachi, Japan), and Kouichi Sakurai (Kyushu Uni, Japan) Certificates of Recoverability with Scalable Recovery Agent Security ......258 Eric R. Verheul (PricewaterhouseCoopers, The Netherlands) Design Validations for Discrete Logarithm Based Signature Schemes ......276 Ernest Brickell (Intel, USA), David Pointcheval (ENS, France), Serge Vaudenay (EPFL, Switzerland), and Moti Yung (Certco, USA) Optimally Efficient Accountable Time-Stamping ..........................293 Ahto Buldas, Helger Lipmaa (Ku¨berneetika AS, Estonia), and Berry Schoenmakers (Eindhoven Uni of Tech, The Netherlands) “PseudorandomIntermixing”: A Tool for Shared Cryptography ...........306 Yair Frankel (CertCo, USA), Philip MacKenzie (Bell Labs, USA), and Moti Yung (CertCo, USA) RSA-Based Auto-recoverable Cryptosystems ..............................326 Adam Young (Columbia Uni, USA), and Moti Yung (CertCo, USA) Efficient and Fresh Certification ..........................................342 Irene Gassko (Bell Labs, USA), Peter S. Gemmell (Uni of New Mexico, USA), and Philip MacKenzie (Bell Labs, USA)