Public Key Cryptography

ThePKC 99conference,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 PKC 99 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 ANewTypeof\MagicInk"Signatures Towards Transcript-IrrelevantAnonymityRevocation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 FengBaoandRobertH. Deng(KentRidgeDigitalLabs,Singapore) ANewAspectofDualBasisforE cientFieldArithmetic . . . . . . . . . . . . . . . . . 12 Chang-HyiLee(SAIT,Korea) Jong-InLim(KoreaUni) OntheSecurityofRandomSources. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Jean-S ebastienCoron(ENSandGemplus,France) AnonymousFingerprintingBasedonCommitted ObliviousTransfer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 JosepDomingo-Ferrer(UniRoviraiVirgili,Spain) HowtoEnhancetheSecurityofPublic-Key EncryptionatMinimumCost. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 EiichiroFujisakiandTatsuakiOkamoto(NTT,Japan) EncryptedMessageAuthenticationbyFirewalls. . . . . . . . . . . . .