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