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 ANewTypeofMagicInk"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. . . . . . . . . . .
A New Type of "Magic Ink" Signatures - Towards Transcript-Irrelevant Anonymity Revocation.- A New Aspect of Dual Basis for Efficient Field Arithmetic.- On the Security of Random Sources.- Anonymous Fingerprinting Based on Committed Oblivious Transfer.- How to Enhance the Security of Public-Key Encryption at Minimum Cost.- Encrypted Message Authentication by Firewalls.- A Relationship between One-Wayness and Correlation Intractability.- Message Recovery Fair Blind Signature.- On Quorum Controlled Asymmetric Proxy Re-encryption.- Mini-Cash: A Minimalistic Approach to E-Commerce.- Preserving Privacy in Distributed Delegation with Fast Certificates.- Unknown Key-Share Attacks on the Station-to-Station (STS) Protocol.- Toward Fair International Key Escrow.- How to Copyright a Function?.- On the Security of RSA Screening.- The Effectiveness of Lattice Attacks Against Low-Exponent RSA.- A Trapdoor Permutation Equivalent to Factoring.- Low-Cost Double-Size Modular Exponentiation or How to Stretch Your Cryptoprocessor.- Evaluating Differential Fault Analysis of Unknown Cryptosystems.- Removing Interoperability Barriers Between the X.509 and EDIFACT Public Key Infrastructures: The DEDICA Project.- Hash Functions and the MAC Using All-or-Nothing Property.- Decision Oracles are Equivalent to Matching Oracles.- Shared Generation of Random Number with Timestamp: How to Cope with the Leakage of the CA's Secret.- Auto-Recoverable Cryptosystems with Faster Initialization and the Escrow Hierarchy.- A Secure Pay-per-View Scheme for Web-Based Video Service.