Advances in Cryptology - CRYPTO 2000

Crypto2000wasthe20thAnnualCryptoconference. Itwassponsoredbythe InternationalAssociationforCryptologicResearch(IACR)incooperationwith theIEEEComputerSocietyTechnicalCommitteeonSecurityandPrivacyand theComputerScienceDepartmentoftheUniversityofCaliforniaatSantaB- bara. Theconferencereceived120submissions,andtheprogramcommittee- lected32oftheseforpresentation. Extendedabstractsofrevisedversionsof thesepapersareintheseproceedings. Theauthorsbearfullresponsibilityfor thecontentsoftheirpapers. Theconferenceprogramincludedtwoinvitedlectures. DonCoppersmith s presentation ThedevelopmentofDES recordedhisinvolvementwithoneof themostimportantcryptographicdevelopmentsever,namelytheDataEncr- tionStandard,andwasparticularlyaptgiventheimminentselectionofthe AdvancedEncryptionStandard. Mart ?nAbadi spresentation Tamingthe- versary wasaboutbridgingthegapbetweenusefulbutperhapssimplisticthreat abstractionsandrigorousadversarialmodels,orperhaps,evenmoregenerally, betweenviewpointsofthesecurityandcryptographycommunities. Anabstract correspondingtoMart ?n stalkisincludedintheseproceedings. Theconferenceprogramalsoincludeditstraditional rumpsession ofshort, informalorimpromptupresentations,chairedthistimebyStuartHaber. These presentationsarenotre?ectedintheseproceedings. Anelectronicsubmissionprocesswasavailableandrecommended,butforthe ?rsttimeusedawebinterfaceratherthanemail. (Perhapsasaresult,therewere nohardcopysubmissions. )Thesubmissionreviewprocesshadthreephases. In the?rstphase,programcommitteememberscompiledreports(assistedattheir discretionbysub-refereesoftheirchoice,butwithoutinteractionwithother programcommitteemembers)andenteredthem,viawebforms,intoweb-review softwarerunningatUCSD. Inthesecondphase,committeemembersusedthe softwaretobrowseeachother sreports,discuss,andupdatetheirownreports. Lastlytherewasaprogramcommitteemeetingtodiscussthedi?cultcases. Iamextremelygratefultotheprogramcommitteemembersfortheiren- mousinvestmentoftime,e?ort,andadrenalineinthedi?cultanddelicate processofreviewandselection. (Alistofprogramcommitteemembersands- refereestheyinvokedcanbefoundonsucceedingpagesofthisvolume. )Ialso thanktheauthorsofsubmittedpapers inequalmeasureregardlessofwhether theirpaperswereacceptedornot fortheirsubmissions. Itistheworkofthis bodyofresearchersthatmakesthisconferencepossible. IthankRebeccaWrightforhostingtheprogramcommitteemeetingatthe AT&TbuildinginNewYorkCityandmanagingthelocalarrangements,and RanCanettifororganizingthepost-PC-meetingdinnerwithhischaracteristic gastronomicandoenophilic?air. VI Preface Theweb-reviewsoftwareweusedwaswrittenforEurocrypt2000byWim MoreauandJorisClaessensunderthedirectionofEurocrypt2000programchair BartPreneel,andIthankthemforallowingustodeploytheirusefulandcolorful tool. IammostgratefultoChanathipNamprempre(aka. Meaw)whoprovided systems,logistical,andmoralsupportfortheentireCrypto2000process. She wrotethesoftwarefortheweb-basedsubmissions,adaptedandranthew- reviewsoftwareatUCSD,andcompiledthe?nalabstractsintotheproceedings youseehere. ShetypesfasterthanIspeak. IamgratefultoHugoKrawczykforhisinsightandadvice,providedovera longperiodoftimewithhisusualcombinationofhonestyandcharm,andto himandotherpastprogramcommitteechairs,mostnotablyMichaelWiener andBartPreneel,forrepliestothehostofquestionsIposedduringthep- cess. InadditionIreceivedusefuladvicefrommanymembersofourcommunity includingSilvioMicali,TalRabin,RonRivest,PhilRogaway,andAdiShamir. FinallythankstoMattFranklinwhoasgeneralchairwasinchargeofthelocal organizationand?nances,and,ontheIACRside,toChristianCachin,Kevin McCurley,andPaulVanOorschot. ChairingaCryptoprogramcommitteeisalearningprocess. Ihavecometo appreciateevenmorethanbeforethequalityandvarietyofworkinour?eld, andIhopethepapersinthisvolumecontributefurthertoitsdevelopment. June2000 MihirBellare ProgramChair,Crypto2000 CRYPTO2000 August20 24,2000,SantaBarbara,California,USA Sponsoredbythe InternationalAssociationforCryptologicResearch(IACR) incooperationwith IEEEComputerSocietyTechn

Includes supplementary material: sn.pub/extras

Klappentext

softwaretobrowseeachother sreports,discuss,andupdatetheirownreports. Lastlytherewasaprogramcommitteemeetingtodiscussthedi?cultcases. Iamextremelygratefultotheprogramcommitteemembersfortheiren- mousinvestmentoftime,e?ort,andadrenalineinthedi?cultanddelicate processofreviewandselection. (Alistofprogramcommitteemembersands- refereestheyinvokedcanbefoundonsucceedingpagesofthisvolume. )Ialso thanktheauthorsofsubmittedpapers inequalmeasureregardlessofwhether theirpaperswereacceptedornot fortheirsubmissions. Itistheworkofthis bodyofresearchersthatmakesthisconferencepossible. IthankRebeccaWrightforhostingtheprogramcommitteemeetingatthe AT&TbuildinginNewYorkCityandmanagingthelocalarrangements,and RanCanettifororganizingthepost-PC-meetingdinnerwithhischaracteristic gastronomicandoenophilic?air. VI Preface Theweb-reviewsoftwareweusedwaswrittenforEurocrypt2000byWim MoreauandJorisClaessensunderthedirectionofEurocrypt2000programchair BartPreneel,andIthankthemforallowingustodeploytheirusefulandcolorful tool. IammostgratefultoChanathipNamprempre(aka. Meaw)whoprovided systems,logistical,andmoralsupportfortheentireCrypto2000process. She wrotethesoftwarefortheweb-basedsubmissions,adaptedandranthew- reviewsoftwareatUCSD,andcompiledthe?nalabstractsintotheproceedings youseehere. ShetypesfasterthanIspeak. IamgratefultoHugoKrawczykforhisinsightandadvice,providedovera longperiodoftimewithhisusualcombinationofhonestyandcharm,andto himandotherpastprogramcommitteechairs,mostnotablyMichaelWiener andBartPreneel,forrepliestothehostofquestionsIposedduringthep- cess. InadditionIreceivedusefuladvicefrommanymembersofourcommunity includingSilvioMicali,TalRabin,RonRivest,PhilRogaway,andAdiShamir. FinallythankstoMattFranklinwhoasgeneralchairwasinchargeofthelocal organizationand?nances,and,ontheIACRside,toChristianCachin,Kevin McCurley,andPaulVanOorschot. ChairingaCryptoprogramcommitteeisalearningprocess. Ihavecometo appreciateevenmorethanbeforethequalityandvarietyofworkinour?eld, andIhopethep

Inhalt
XTR and NTRU.- The XTR Public Key System.- A Chosen-Ciphertext Attack against NTRU.- Privacy for Databases.- Privacy Preserving Data Mining.- Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing.- Secure Distributed Computation and Applications.- Parallel Reducibility for Information-Theoretically Secure Computation.- Optimistic Fair Secure Computation.- A Cryptographic Solution to a Game Theoretic Problem.- Algebraic Cryptosystems.- Differential Fault Attacks on Elliptic Curve Cryptosystems.- Quantum Public-Key Cryptosystems.- New Public-Key Cryptosystem Using Braid Groups.- Message Authentication.- Key Recovery and Forgery Attacks on the MacDES MAC Algorithm.- CBC MACs for Arbitrary-Length Messages: The Three-Key Constructions.- L-collision Attacks against Randomized MACs.- Digital Signatures.- On the Exact Security of Full Domain Hash.- Timed Commitments.- A Practical and Provably Secure Coalition-Resistant Group Signature Scheme.- Provably Secure Partially Blind Signatures.- Cryptanalysis.- Weaknesses in the SL2( ) Hashing Scheme.- Fast Correlation Attacks through Reconstruction of Linear Polynomials.- Traitor Tracing and Broadcast Encryption.- Sequential Traitor Tracing.- Long-Lived Broadcast Encryption.- Invited Talk.- Taming the Adversary.- Symmetric Encryption.- The Security of All-or-Nothing Encryption: Protecting against Exhaustive Key Search.- On the Round Security of Symmetric-Key Cryptographic Primitives.- New Paradigms for Constructing Symmetric Encryption Schemes Secure against Chosen-Ciphertext Attack.- To Commit or Not to Commit.- Efficient Non-malleable Commitment Schemes.- Improved Non-committing Encryption Schemes Based on a General Complexity Assumption.- Protocols.- A Note on the Round-Complexity of Concurrent Zero-Knowledge.- An Improved Pseudo-random Generator Based on Discrete Log.- Linking Classical and Quantum Key Agr…