Public Key Cryptography : Second International Workshop on Practice and Theory in Public Key Cryptography

ThePKC99conference, heldintheancientcapitalofKamakura, Japan, March 1-3,1999, representsthesecondconferenceintheinternationalworkshopseries dedicatedtothepracticeandtheoryinpublickeycryptography. Theprogramcommitteeoftheconferencereceived61submissionsfrom12co- triesandregions(Australia, Canada, Finland, France, Japan, SaudiArabia, S- gapore, Spain, Taiwan, UK, USA, andYugoslavia), ofwhich25wereselectedfor presentation. Allsubmissionswerereviewedbyexpertsintherelevantareas. TheprogramcommitteeconsistedofChin-ChenChangoftheNationalChung ChengUniversity, Taiwan, YvoDesmedtoftheUniversityofWisconsin-Milwaukee, USA, HidekiImai(Co-Chair)oftheUniversityofTokyo, Japan, MarkusJak- sson of Bell Labs, USA, Kwangjo Kim of Information and Communications University, Korea, Arjen Lenstra of Citibank, USA, Tsutomu Matsumoto of YokohamaNationalUniversity, Japan, EijiOkamotoofJAIST, Japan, Tatsuaki OkamotoofNTT, Japan, NigelSmartofHPLabsBristol, UK, andYuliang Zheng(Co-Chair)ofMonashUniversity, Australia. Membersofthecommittee spentnumeroushoursinreviewingthesubmissionsandprovidingadviceand commentsontheselectionofpapers. Wewouldliketotakethisopportunityto thankallthemembersfortheirinvaluablehelpinproducingsuchahighquality technicalprogram. Theprogramcommitteealsoaskedexpertadviceofmanyoftheircolleagues, - cluding: MasayukiAbe, KazumaroAoki, DanielBleichenbacher, AtsushiFujioka, EiichiroFujisaki, ChandanaGamage, BrianKing, KunioKobayashi, Tetsutaro Kobayashi, PhilMacKenzie, HidemiMoribatake, KazuoOhta, AminShokr- lahi, ShigenoriUchiyama, andYonggeWang. Wethankthemallfortheirhelp. Theconferencewouldnothavebeensuccessfulwithouttheskillfulassistance ofthemembersoftheorganizingcommittee. OurspecialthanksgotoTakashi ManoofIPA, Japan, KantaMatsuuraandHidenoriShida, bothofUniversity ofTokyo, Japan. Last, butnotleast, wewouldliketothankallthepeoplewhosubmittedtheir paperstotheconference(includingthosewhosesubmissionswerenotsuccessful), aswellastheworkshopparticipantsfromaroundtheworld, fortheirsupport whichmadethisconferencepossible. March1999 UniversityofTokyo, Japan HidekiImai MonashUniversity, Melbourne, Australia YuliangZheng PKC99 1999InternationalWorkshop onPracticeandTheory inPublicKeyCryptography KamakuraPrinceHotel, Kamakura, Japan March1-3,1999 Incooperationwith TheTechnicalGrouponInformationSecurity, theInstituteof Electronics, InformationandCommunicationEngineers(IEICE) OrganizingCommittee HidekiImai, Chair (UniversityofTokyo, Japan) TakashiMano (IPA, Japan) KantaMatsuura (UniversityofTokyo, Japan) HidenoriShida (UniversityofTokyo, Japan) YuliangZheng (MonashUniversity, Australia) ProgramCommittee HidekiImai, Co-Chair (UniversityofTokyo, Japan) YuliangZheng, Co-Chair (MonashUniversity, Australia) Chin-ChenChang (NationalChungChengUniversity, Taiwan) YvoDesmedt (UniversityofWisconsin-Milwaukee, USA) KwangjoKim (InformationandCommunicationsUniversity, Korea) MarkusJakobsson (BellLabs, USA) ArjenLenstra (Citibank, USA) TsutomuMatsumoto (YokohamaNationalUniversity, Japan) EijiOkamoto (JAIST, Japan) TatsuakiOkamoto (NTT, Japan) NigelSmart (HPLabsBristol, UK) Contents ANewTypeofMagicInk"SignaturesTowards Transcript-IrrelevantAnonymityRevocation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 FengBaoandRobertH. Deng(KentRidgeDigitalLabs, Singapore) ANewAspectofDualBasisforE cientFieldArithmetic . . . . . . . . . . . . . . . . . 12 Chang-HyiLee(SAIT, Korea) Jong-InLim(KoreaUni) OntheSecurityofRandomSources. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Jean-S ebastienCoron(ENSandGemplus, France) Anonymou