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 IEEEComputerSocietyTechnicalCommitteeonSecurityandPrivacy, ComputerScienceDepartment,UniversityofCalifornia,SantaBarbara GeneralChair MatthewFranklin,XeroxPaloAltoResearchCenter,USA ProgramChair MihirBellare,UniversityofCalifornia,SanDiego,USA ProgramCommittee AlexBiryukov. . . . . . . . . . . . . . . . . . . . . . . . . . WeizmannInstituteofScience,Israel DanBoneh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . StanfordUniversity,USA ChristianCachin. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IBMResearch,Switzerland RanCanetti. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IBMResearch,USA RonaldCramer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ETHZurich,Switzerland YairFrankel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CertCo,USA ShaiHalevi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IBMResearch,USA ArjenLenstra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Citibank,USA MitsuruMatsui. . . . . . . . . . . . . . . . . . . . . . MitsubishiElectricCorporation,Japan PaulVanOorschot. . . . . . . . . . . . . . . . . . . . . . . . . . . . . EntrustTechnologies,Canada BartPreneel. . . . . . . . . . . . . . . . . . . . . . . . KatholiekeUniversiteitLeuven,Belgium PhillipRogaway. . . . . . . . . . . . . . . . . . . . . . . . UniversityofCalifornia,Davis,USA VictorShoup. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IBMZurich,Switzerland JessicaStaddon. . . . . . . . . . . . . . . . . . . . . . . . . BellLabsResearch,PaloAlto,USA JacquesStern. . . . . . . . . . . . . . . . . . . . . . . . . . . . . EcoleNormaleSup´erieure,France DougStinson. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . UniversityofWaterloo,Canada SalilVadhan. . . . . . . . . . . . . . . . . . . . MassachusettsInstituteofTechnology,USA DavidWagner. . . . . . . . . . . . . . . . . . . . . . . . UniversityofCalifornia,Berkeley,USA RebeccaWright. . . . . . . . . . . . . . . . . . . . . . . . . . AT&TLaboratoriesResearch,USA Advisorymembers MichaelWiener(Crypto1999programchair). . EntrustTechnologies,Canada JoeKilian(Crypto2001programchair). . . . . . . . . . . . . . . . . . Intermemory,USA VIII Organization Sub-Referees BillAiello,JeeheaAn,OlivierBaudron,DonBeaver,JoshBenaloh,JohnBlack, SimonBlackburn,AlexandraBoldyreva,NikitaBorisov,VictorBoyko,Jan- menisch,SureshChari,ScottContini,DonCoppersmith,ClaudeCr´epeau,Ivan Damg?ard,AnandDesai,GiovanniDiCrescenzo,YevgeniyDodis,Matthias Fitzi,MattFranklin,RosarioGennaro,GuangGong,LuisGranboulan,Nick Howgrave-Graham,RussellImpagliazzo,YuvalIshai,MarkusJakobsson,Stas Jarecki,ThomasJohansson,CharanjitJutla,JoeKilian,EyalKushilevitz,Moses Liskov,StefanLucks,AnnaLysyanskaya,PhilipMacKenzie,SubhamoyMaitra, TalMalkin,BarbaraMasucci,AlfredMenezes,DanieleMicciancio,SaraMiner, IliaMironov,MoniNaor,PhongNguyen,RafailOstrovsky,ErezPetrank,Birgit P?tzmann,BennyPinkas,DavidPointcheval,GuillaumePoupard,TalRabin, CharlieRacko?,Zul?karRamzan,OmerReingold,LeoReyzin,PankajRohatgi, AmitSahai,LouisSalvail,ClausSchnorr,MikeSemanko,BobSilverman,Joe Silverman,DanSimon,NigelSmart,BenSmeets,AdamSmith,MartinStrauss, GaneshSundaram,SergeVaudenay,FrederikVercauteren,BernhardvonSt- gel,RuizhongWei,SusanneGudrunWetzel,ColinWilliams,StefanWolf,Felix Wu,YiqunLisaYin,AmirYoussef,RobertZuccherato TableofContents XTRandNTRU TheXTRPublicKeySystem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 ArjenK. Lenstra,EricR. Verheul AChosen-CiphertextAttackagainstNTRU. . . . . . . . . . . . . . . . . . . . . . . . . . . 20 ´ ElianeJaulmes,AntoineJoux PrivacyforDatabases PrivacyPreservingDataMining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 YehudaLindell,BennyPinkas ReducingtheServersComputationinPrivateInformationRetrieval: PIRwithPreprocessing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 AmosBeimel,YuvalIshai,TalMalkin SecureDistributedComputationandApplications ParallelReducibilityforInformation-TheoreticallySecureComputation. . . 74 YevgeniyDodis,SilvioMicali OptimisticFairSecureComputation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 ChristianCachin,JanCamenisch ACryptographicSolutiontoaGameTheoreticProblem. . . . . . . . . . . . . . . . 112 YevgeniyDodis,ShaiHalevi,TalRabin AlgebraicCryptosystems Di?erentialFaultAttacksonEllipticCurveCryptosystems. . . . . . . . . . . . . . 131 IngridBiehl,BerndMeyer,VolkerMul ¨ler QuantumPublic-KeyCryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 TatsuakiOkamoto,KeisukeTanaka,ShigenoriUchiyama NewPublic-KeyCryptosystemUsingBraidGroups . . . . . . . . . . . . . . . . . . . . 166 KiHyoungKo,SangJinLee,JungHeeCheon,JaeWooHan, Ju-sungKang,ChoonsikPark MessageAuthentication KeyRecoveryandForgeryAttacksontheMacDESMACAlgorithm . . . . . 184 DonCoppersmith,LarsR. Knudsen,ChrisJ. Mitchell X TableofContents CBCMACsforArbitrary-LengthMessages:TheThree-KeyConstructions 197 JohnBlack,PhillipRogaway L-collisionAttacksagainstRandomizedMACs. . . . . . . . . . . . . . . . . . . . . . . . . 216 MichaelSemanko DigitalSignatures OntheExactSecurityofFullDomainHash. . . . . . . . . . . . . . . . . . . . . . . . . . . 229 Jean-S´ ebastienCoron TimedCommitments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 DanBoneh,MoniNaor APracticalandProvably SecureCoalition-ResistantGroupSignatureScheme. . . . . . . . . . . . . . . . . . . . 255 GiuseppeAteniese,JanCamenisch,MarcJoye,GeneTsudik ProvablySecurePartiallyBlindSignatures. . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 MasayukiAbe,TatsuakiOkamoto Cryptanalysis n WeaknessesintheSL (IF )HashingScheme. . . . . . . . . . . . . . . . . . . . . . . . . . 287 2 2 RainerSteinwandt,MarkusGrassl,WilliGeiselmann,ThomasBeth FastCorrelationAttacksthroughReconstructionofLinearPolynomials . . 300 ThomasJohansson,FredrikJ¨ onsson TraitorTracingandBroadcastEncryption SequentialTraitorTracing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .