Advances in Cryptology - CRYPTO 2000

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.