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. . . . 154 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 . . . . . . . . . . . . . 245 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.