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"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