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...69 ChandanaGamage,JussipekkaLeiwoand YuliangZheng(MonashUni,Australia) ARelationshipbetweenOne-Waynessand CorrelationIntractability...82 SatoshiHadaandToshiakiTanaka(KDD,Japan) MessageRecoveryFairBlindSignature ...97 Hyung-WooLeeandTai-YunKim(KoreaUni) OnQuorumControlledAsymmetricProxyRe-encryption...112 MarkusJakobsson(BellLabs,USA) Mini-Cash:AMinimalisticApproachtoE-Commerce...122 MarkusJakobsson(BellLabs,USA) PreservingPrivacyinDistributedDelegation withFastCerti cates ...136 PekkaNikander(Ericsson,Finland) YkiKortesniemiandJonnaPartanen(HelsinkiUniofTech,Finland) UnknownKey-ShareAttacksontheStation-to-Station(STS)Protocol...1 54 SimonBlake-Wilson(Certicom,Canada) AlfredMenezes(UniofWaterloo,Canada) TowardFairInternationalKeyEscrow{AnAttemptbyDistributed TrustedThirdAgencieswithThresholdCryptography{ ...171 ShingoMiyazaki(KyushuUniv,Japan) IkukoKuroda(NTT,Japan) KouichiSakurai(KyushuUniv,Japan) HowtoCopyrightaFunction?...188 DavidNaccache(Gemplus,France) AdiShamir(WeizmannInstofSci,Israel) JulienP. Stern(UCL,Belgium,andUnideParis-Sud,France) OntheSecurityofRSAScreening...197 Jean-S ebastienCoron(ENSandGemplus,France) DavidNaccache(Gemplus,France) TheE ectivenessofLatticeAttacksAgainstLow-ExponentRSA ...204 ChristopheCoup e(ENSdeLyon,France) PhongNguyenandJacquesStern(ENSParis,France) ATrapdoorPermutationEquivalenttoFactoring...219 PascalPaillier(GemplusandENST,France) Low-CostDouble-SizeModularExponentiation orHowtoStretchYourCryptoprocessor...223 PascalPaillier(GemplusandENST,France) EvaluatingDi erentialFaultAnalysisofUnknownCryptosystems ...235 PascalPaillier(GemplusandENST,France) RemovingInteroperabilityBarriersBetweentheX. 509and EDIFACTPublicKeyInfrastructures:TheDEDICAProject ...2 45 MontseRubia,JuanCarlosCruellasand ManelMedina(PolytechUniofCatalonia,Spain) HashFunctionsandtheMACUsingAll-or-NothingProperty...263 SangUkShinandKyungHyuneRhee(PuKyongNatUni,Korea) JaeWooYoon(ETRI,Korea) DecisionOraclesareEquivalenttoMatchingOracles...276 HelenaHandschuh(GemplusandENST,France) YiannisTsiounis(GTELabs,USA) MotiYung(CertCo,USA) SharedGenerationofRandomNumberwithTimestamp: HowtoCopewiththeLeakageoftheCA'sSecret ...290 YujiWatanabeandHidekiImai(UniofTokyo,Japan) Auto-RecoverableCryptosystemswithFasterInitialization andtheEscrowHierarchy ...306 AdamYoung(ColumbiaUni,USA) MotiYung(CertCo,USA) ASecurePay-per-ViewSchemeforWeb-BasedVideoService ...315 JianyingZhou(KentRidgeDigitalLabs,Singapore) Kwok-YanLam(NatUniofSingapore) AuthorIndex ...327 ANewTypeof\MagicInk"Signatures| TowardsTranscript-IrrelevantAnonymity Revocation Feng Bao and Robert H. Deng Information Security Group Kent Ridge Digital Labs Singapore 119613 fbaofeng,dengg@krdl. org.

Table of Contents:
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.