Public Key Cryptography: Second International Workshop on Practice and Theory in Public Key Cryptography, PKC'99, Kamakura, Japan, March 1-3, 1999, Proceedings (Lecture Notes in Computer Science)

This book constitutes the refereed proceedings of the Second International Workshop on Practice and Theory in Public Key Cryptography, PKC'99, held in Kamakura, Japan in March 1999. The 25 revised full papers presented were carefully reviewed and selected from a total of 61 submissions. The volume reports most recent research results on all relevant aspects in public key cryptography. Among the topics covered are digital signatures, anonymous finger printing, message authentication, digital payment, key escrow, RSA systems, hash functions, decision oracles, random numbers, finite field computations, pay-per-view-systems, and electronic commerce. 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\magicinksignatures|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\magicinksignatures| Towardstranscript-irrelevantanonymity Revocation Feng Bao And Robert H. Deng Information Security Group Kent Ridge Digital Labs Singapore 119613 Fbaofeng,dengg@krdl. Org. 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. Hideki Imai, Yuliang Zheng, Eds. Includes Bibliographical References And Index. A New Type of “Magic Ink” Signatures — Towards Transcript-Irrelevant Anonymity Revocation....Pages 1-11 A New Aspect of Dual Basis for Efficient Field Arithmetic....Pages 12-28 On the Security of Random Sources....Pages 29-42 Anonymous Fingerprinting Based on Committed Oblivious Transfer....Pages 43-52 How to Enhance the Security of Public-Key Encryption at Minimum Cost....Pages 53-68 Encrypted Message Authentication by Firewalls....Pages 69-81 A Relationship between One-Wayness and Correlation Intractability....Pages 82-96 Message Recovery Fair Blind Signature....Pages 97-111 On Quorum Controlled Asymmetric Proxy Re-encryption....Pages 112-121 Mini-Cash: A Minimalistic Approach to E-Commerce....Pages 122-135 Preserving Privacy in Distributed Delegation with Fast Certificates....Pages 136-153 Unknown Key-Share Attacks on the Station-to-Station (STS) Protocol....Pages 154-170 Toward Fair International Key Escrow....Pages 171-187 How to Copyright a Function?....Pages 188-196 On the Security of RSA Screening....Pages 197-203 The Effectiveness of Lattice Attacks Against Low-Exponent RSA....Pages 204-218 A Trapdoor Permutation Equivalent to Factoring....Pages 219-222 Low-Cost Double-Size Modular Exponentiation or How to Stretch Your Cryptoprocessor....Pages 223-234 Evaluating Differential Fault Analysis of Unknown Cryptosystems....Pages 235-244 Removing Interoperability Barriers Between the X.509 and EDIFACT Public Key Infrastructures: The DEDICA Project....Pages 245-262 Hash Functions and the MAC Using All-or-Nothing Property....Pages 263-275 Decision Oracles are Equivalent to Matching Oracles....Pages 276-289 Shared Generation of Random Number with Timestamp: How to Cope with the Leakage of the CA’s Secret....Pages 290-305 Auto-Recoverable Cryptosystems with Faster Initialization and the Escrow Hierarchy....Pages 306-314 A Secure Pay-per-View Scheme for Web-Based Video Service....Pages 315-326