Advances in Cryptology – EUROCRYPT 2002

YouarereadingtheproceedingsofEUROCRYPT2002,the21stannualEu- cryptconference. TheconferencewassponsoredbytheIACR,theInternational AssociationofCryptologicResearch, www. iacr. org,thisyearincooperation withtheCodingandCryptogroupattheTechnicalUniversityofEindhovenin TheNetherlands. TheGeneralChair,BerrySchoenmakers,wasresponsiblefor thelocalorganization,andtheconferenceregistrationwashandledbytheIACR SecretariatattheUniversityofCalifornia,SantaBarbara,USA. IthankBerry Schoenmakersforallhisworkandforthepleasantcollaboration. Atotalof122papersweresubmittedofwhich33wereacceptedforpres- tationattheconference. Oneofthepapersisaresultofamergeroftwosubm- sions. Threeadditionalsubmissionswerewithdrawnbytheauthorsshortlyafter thesubmissiondeadline. TheprogramalsolistsinvitedtalksbyJoanDaemen andVincentRijmen("AESandtheWideTrailStrategy")andStephenKent ("RethinkingPKI:What'sTrustGotToDowithIt?"). Also,therewasarump (recentresults)session,whichHenkvanTilborgkindlyagreedtochair. Thereviewingprocesswasachallengingtaskandmanygoodsubmissionshad toberejected. Eachpaperwasreviewedbyatleastthreemembersoftheprogram committee,andpapersco-authoredbyamemberofthecommitteewerereviewed byatleast?veothermembers.Inmostcasesextensivecommentswerepassed ontotheauthors. Itwasapleasureformetoworkwiththeprogramcommittee, whosemembersallworkedveryhardoverseveralmonths. Thereviewingprocess was?nalizedwithameetinginCopenhagen,onJanuary13th,2002. Iamverygratefultothemanyadditionalreviewerswhocontributedwith theirexpertise:AdamBack,AlfredMenezes,AliceSilverberg,AntonStiglic, AntoonBosselaers,AriJuels,BarryTrager,CarloBlundo,ChanSupPark, ChongHeeKim,ChristianPaquin,ChristopheDeCanni'ere,CraigGentry,Dae HyunYum,DanBernstein,DarioCatalano,DavidPointcheval,DavidWagner, DongJinPark,DorianGoldfeld,ElianeJaulmes,EmmanuelBresson,Florian Hess,FrederikVercauteren,Fr'ed'ericL'egar'e,Fr'ed'ericValette,GlennDurfee, GuillaumePoupard,GwenaelleMartinet,HanPilKim,HeinRoehrig,Hovav Shacham,IlyaMironov,JacquesStern,JaeEunKang,JanCamenisch,Jean- FrancoisRaymond,JensJensen,JesperBuusNielsen,JimHughes,JohnMalone- Lee,JonathanPoritz,JongHoonShin,KatsuyukiTakashima,KazueSako, KennyPaterson,KyungWeonKim,LeoReyzin,LouisGranboulan,LouisS- vail,Markku-JuhaniO.Saarinen,MattRobshaw,MichaelQuisquater,Michael Waidner,MichelMitton,MikeSzydlo,MikeWiener,MotiYung,OlivierB- dron,OmerReingold,PaulDumais,PaulKocher,PhilippeChose,Philippe Golle,Pierre-AlainFouque,RanCanetti,RichardJozsa,RonaldCramer,Sang GyooSim,SangJinLee,SergeFehr,ShirishAltekar,SimonBlackburn,Stefan Wolf,StevenGalbraith,SvetlaNikova,TaeGuKim,TalMalkin,TalRabin, TetsuIwata,ToshioHasegawa,TsuyoshiNishioka,VirgilGligor,WenboMao, YeonKyuPark,YiqunLisaYin,YongHoHwang,YuvalIshai. VI Myworkasprogramchairwasmadealoteasierbytheelectronicsubm- sionsoftwarewrittenbyChanathipNamprempreforCrypto2000withmod- cationsbyAndreAdelsbachforEurocrypt2001,andbythereviewingsoftware developedandwrittenbyBartPreneel,WimMoreau,andJorisClaessensfor Eurocrypt2000. IwouldliketothankOledaSilvaSmithforsettingupallthis softwarelocallyandforthehelpwiththeproblemsIencountered. Iamalso gratefultoWimMoreauandChanathipNamprempreforsolvingsomeofthe problemswehadwiththesoftware. OnbehalfofthegeneralchairIwouldliketoextendmygratitudetothe membersofthelocalorganizingcommitteeatTUEindhoven,inparticularto PeterRoelseandGergelyAlp'ar. For?nancialsupportoftheconferencethe- ganizingcommitteegratefullyacknowledgesthisyear'ssponsors:PhilipsSe- conductorsCryptologyCompetenceCenter,MitsubishiElectricCorporation,cv cryptovision,Cryptomathic,ERCIM,CMG,Sectra,EUFORCE,andEIDMA.Finally,athank-yougoestoallwhosubmittedpaperstothisconferenceand lastbutnotleasttomyfamilyfortheirloveandunderstanding. February2002 LarsKnudsen EUROCRYPT2002 April28-May2,2002,Amsterdam,TheNetherlands Sponsoredbythe InternationalAssociationofCryptologicResearch(IACR) incooperationwith TheCodingandCryptogroupattheTechnicalUniversity ofEindhoveninTheNetherlands GeneralChair BerrySchoenmakers,DepartmentofMathematicsandComputingScience, TechnicalUniversityofEindhoven,TheNetherlands ProgramChair LarsR. Knudsen,DepartmentofMathematics, TechnicalUniversityofDenmark ProgramCommittee DanBoneh...StanfordUniversity,USA StefanBrands...McGillUniversitySchoolofComputerScience, Montreal,Canada ChristianCachin...IBMResearch,Zurich,Switzerland DonCoppersmith...IBMResearch,USA IvanDamg?ard...AarhusUniversity,Denmark AnandDesai...NTTMultimediaCommunicationsLaboratories,USA RosarioGennaro...IBMResearch,USA AlainHiltgen...UBS,Switzerland MarkusJakobsson ...RSALaboratories,USA ThomasJohansson...UniversityofLund,Sweden AntoineJoux...DCSSI,France PilJoongLee...Postech,Korea ArjenLenstra...CitibankandTechnicalUniversityofEindhoven KeithMartin...RoyalHolloway,UniversityofLondon,UK MitsuruMatsui...MitsubishiElectric,Japan PhongQ.Nguyen...CNRS/EcoleNormaleSup'erieure,France KaisaNyberg...NokiaResearchCenter,Finland BartPreneel...KatholiekeUniversiteitLeuven,Belgium ReihanehSafavi-Naini...UniversityofWollongong,Australia NigelSmart...UniversityofBristol,UK PaulVanOorschot...CarletonUniversity,Canada RebeccaWright...DIMACS,USA TableofContents CryptanalysisI CryptanalysisofaPseudorandomGeneratorBasedonBraidGroups ...1 RosarioGennaro,DanieleMicciancio PotentialWeaknessesoftheCommutatorKeyAgreementProtocol BasedonBraidGroups...14 SangJinLee,EonkyungLee ExtendingtheGHSWeilDescentAttack ...29 StevenD. Galbraith,FlorianHess,NigelP. Smart Public-KeyEncryption UniversalHashProofsandaParadigm forAdaptiveChosenCiphertextSecurePublic-KeyEncryption ...45 RonaldCramer,VictorShoup Key-InsulatedPublicKeyCryptosystems ...65 YevgeniyDodis,JonathanKatz,ShouhuaiXu,MotiYung OntheSecurityofJointSignatureandEncryption...83 JeeHeaAn,YevgeniyDodis,TalRabin InvitedTalk AESandtheWideTrailDesignStrategy ...108 JoanDaemen,VincentRijmen InformationTheory&NewModels IndistinguishabilityofRandomSystems...110 UeliMaurer HowtoFoolanUnboundedAdversarywithaShortKey...133 AlexanderRussell,HongWang CryptographyinanUnboundedComputationalModel...149 DavidP. Woodru?,MartenvanDijk X Table of Contents ImplementationalAnalysis PerformanceAnalysisandParallelImplementation ofDedicatedHashFunctions ...165 JunkoNakajima,MitsuruMatsui FaultInjectionandaTimingChannelonanAnalysisTechnique...181 JohnA. Clark,JeremyL. Jacob SpeedingUpPointMultiplicationonHyperellipticCurves withE?ciently-ComputableEndomorphisms ...197 Young-HoPark,SangtaeJeong,JonginLim StreamCiphers FastCorrelationAttacks:AnAlgorithmicPointofView ...209 PhilippeChose,AntoineJoux,MichelMitton BDD-BasedCryptanalysisofKeystreamGenerators...222 MatthiasKrause LinearCryptanalysisofBluetoothStreamCipher ...238 JovanDj. Goli'c,VittorioBagini,GuglielmoMorgari DigitalSignaturesI GenericLowerBoundsforRootExtractionandSignatureSchemes inGeneralGroups ...256 IvanDamg?ard,MaciejKoprowski OptimalSecurityProofsforPSSandOtherSignatureSchemes ...272 Jean-S'ebastienCoron CryptanalysisII CryptanalysisofSFLASH...288 HenriGilbert,MarineMinier CryptanalysisoftheRevisedNTRUSignatureScheme...299 CraigGentry,MikeSzydlo Table of Contents XI KeyExchange DynamicGroupDi?e-HellmanKeyExchange underStandardAssumptions...321 EmmanuelBresson,OlivierChevassut,DavidPointcheval UniversallyComposableNotionsofKeyExchangeandSecureChannels...337 RanCanetti,HugoKrawczyk OnDeniabilityinQuantumKeyExchange...352 DonaldBeaver ModesofOperation APractice-OrientedTreatmentofPseudorandomNumberGenerators ...