TheInternationalWorkshoponPracticeandTheoryinPublicKeyCryptog- phyPKC2002washeldattheMaisondelaChimie,situatedintheverycenter ofParis,FrancefromFebruary12to14,2002. ThePKCseriesofconferences yearlyrepresentsinternationalresearchandthelatestachievementsinthearea ofpublickeycryptography,coveringawidespectrumoftopics,fromcryptos- temstoprotocols,implementationtechniquesorcryptanalysis. Afterbeingheld infoursuccessiveyearsinpaci?c-asiancountries,PKC2002experiencedforthe ?rsttimeaEuropeanlocation,thusshowingitsabilitytoreachaneverwider audiencefromboththeindustrialcommunityandacademia. Weareverygratefultothe19membersoftheProgramCommitteefortheir hardande?cientworkinproducingsuchahighqualityprogram. Inresponseto thecallforpapersofPKC2002,69paperswereelectronicallyreceivedfrom13 di?erentcountriesthroughoutEurope,America,andtheFarEast. Allsubm- sionswerereviewedbyatleastthreemembersoftheprogramcommittee,who eventuallyselectedthe26papersthatappearintheseproceedings. Inaddition to this program, we were honored to welcome Prof. Bart Preneel who kindly acceptedtogivethisyear'sinvitedtalk. Theprogramcommitteegratefully- knowledgesthehelpofalargenumberofcolleagueswhoreviewedsubmissionsin theirareaofexpertise:MasayukiAbe,SeigoArita,OlivierBaudron,MihirB- lare,EmmanuelBresson,EricBrier,MathieuCiet,AlessandroCon?itti,Jean- S'ebastienCoron,RogerFischlin,Pierre-AlainFouque,MattFranklin,Rosario Genarro,MarcGirault,LouisGranboulan,GoichiroHanaoka,DarrelHank- son, Eliane Jaulmes, Ari Juels, Jinho Kim, Marcos Kiwi, Kazukuni Kobara, Francois Koeune, Byoungcheon Lee, A. K. Lenstra, Pierre Loidreau, Wenbo Mao, Gwenaelle Martinet, Yi Mu, Phong Nguyen, Satoshi Obana, Guillaume Poupard,YasuyukiSakai,HideoShimizu,TomShrimpton,RonSteinfeld,K- suyukiTakashima,HuaxiongWang,andYujiWatanabe. JulienBrouchier- servesspecialthanksforskillfullymaintainingtheprogramcommittee'swebsite andpatientlyhelpingoutduringtherefereeingprocess. Finally,wewishtothankalltheauthorswhocommittedtheirtimebys- mitting papers (including those whose submissions were not successful), thus makingthisconferencepossible,aswellastheparticipants,organizers,andc- tributorsfromaroundtheworldfortheirkindsupport. December2001 DavidNaccache,PascalPaillier PKC2002 FifthInternationalWorkshop onPracticeandTheory inPublicKeyCryptography MaisondelaChimie,Paris,France February12-14,2002 ProgramCommittee DavidNaccache(ProgramChair)...Gemplus,France DanielBleichenbacher...BellLabs,LucentTechnologies,USA YvoDesmedt ...FloridaStateUniversity,USA MarcFischlin...Goethe-UniversityofFrankfurt,Germany ShaiHalevi...IBMT. J. WatsonResearchCenter,USA MarkusJakobsson ...RSALaboratories,USA AntoineJoux...DCSSI,France BurtKaliski ...RSALaboratories,USA KwangjoKim ...InformationandCommunicationsUniversity,Korea EyalKushilevitz...Technion,Israel PascalPaillier...Gemplus,France ' DavidPointcheval ...EcoleNormaleSup'erieure,France Jean-JacquesQuisquater...Universit'eCatholiquedeLouvain,Belgium PhillipRogaway ...UCDavis,USA KazueSako...NECCorporation,Japan BruceSchneier...CounterpaneInternetSecurity,USA JunjiShikata...UniversityofTokyo,Japan IgorShparlinski ...MacquarieUniversity,Australia MotiYung ...Certco,USA JianyingZhou...OracleCorporation,USA TableofContents EncryptionSchemes NewSemanticallySecurePublic-KeyCryptosystemsfromtheRSA-Primitive 1 KouichiSakurai(KyushuUniversity,Japan),TsuyoshiTakagi (TechnischeUniversit. atDarmstadt,Germany) OptimalChosen-CiphertextSecureEncryption ofArbitrary-LengthMessages...17 Jean-S' ebastien Coron (Gemplus, France), Helena Handschuh (Gemplus,France),MarcJoye(Gemplus,France),PascalPaillier ' (Gemplus,France),DavidPointcheval(EcoleNormaleSup' erieure,France), ChristopheTymen(Gemplus,France) OnSu?cientRandomnessforSecurePublic-KeyCryptosystems...34 Takeshi Koshiba (Fujitsu Laboratories Ltd, Japan) Multi-recipientPublic-KeyEncryptionwithShortenedCiphertext...48 Kaoru Kurosawa (Ibaraki University, Japan) SignatureSchemes E?cientandUnconditionallySecureDigitalSignatures andaSecurityAnalysisofaMultireceiverAuthenticationCode...64 GoichiroHanaoka(UniversityofTokyo,Japan),JunjiShikata (University of Tokyo, Japan), Yuliang Zheng (UNC Charlotte, USA), HidekiImai(UniversityofTokyo,Japan) FormalProofsfortheSecurityofSigncryption...80 JoonsangBaek(MonashUniversity,Australia),RonSteinfeld(Monash University,Australia),YuliangZheng(UNCCharlotte,USA) AProvablySecureRestrictivePartiallyBlindSignatureScheme...99 GregMaitland(QueenslandUniversityofTechnology,Australia), ColinBoyd(QueenslandUniversityofTechnology,Australia) ProtocolsI M+1-stPriceAuctionUsingHomomorphicEncryption...1 15 Masayuki Abe (NTT ISP Labs, Japan), Koutarou Suzuki (NTT ISP Labs,Japan) Client/ServerTradeo?sforOnlineElections...125 Ivan Damg? ard (Aarhus University, Denmark), Mads Jurik (Aarhus University,Denmark) X TableofContents Self-tallyingElectionsandPerfectBallotSecrecy...141 AggelosKiayias(GraduateCenter,CUNY,USA),MotiYung(CertCo, USA) ProtocolsII E?cient1-Out-nObliviousTransferSchemes...159 Wen-GueyTzeng(NationalChiaoTungUniversity,Taiwan) LinearCodeImpliesPublic-KeyTraitorTracing...

This book constitutes the thoroughly refereed post-proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography, SAC 2000, held in Waterloo, Ontario, Canada, in August 2000.The 24 revised full papers presented were selected from 41 submissions and have gone through two rounds of reviewing and revision. The papers are organized in topical sections on cryptanalysis, block ciphers: new designs, elliptic curves and efficient implementations, security protocols and applications, block ciphers and hash functions, Boolean functions and stream ciphers, and public key systems.

Anonymity and unobservability have become key issues in the context of securing privacy on the Internet and in other communication networks. Services that provide anonymous and unobservable access to the Internet are important for electronic commerce applications as well as for services where users want to remain anonymous.This book is devoted to the design and realization of anonymity services for the Internet and other communcation networks. The book offers topical sections on: attacks on systems, anonymous publishing, mix systems, identity management, pseudonyms and remailers. Besides nine technical papers, an introduction clarifying the terminology for this emerging area is presented as well as a survey article introducing the topic to a broader audience interested in security issues.

This book constitutes the refereed proceedings of the 7th Australasian Conference on Information Security and Privacy, ACISP 2002, held in Melbourne, Australia, in July 2002.The 36 revised full papers presented together with one invited paper were carefully reviewed and selected from 94 submissions. The papers are organized in topical sections on key handling, trust and secret sharing, fast computation, cryptanalysis, elliptic curves, advanced encryption standard AES, security management, authentication, oblivious transfer, and dealing with adversaries.

This book constitutes the thoroughly refereed post-proceedings of the 7th International Workshop on Fast Software Encryption, FSE 2000, held in New York City, USA in April 2000.The 21 revised full papers presented were carefully reviewed and selected from a total of 53 submissions. The volume presents topical sections on stream-cipher cryptanalysis, new ciphers, AES cryptanalysis, block-cipher cryptanalysis, and theoretical work.

The Information Security Conference 2001 brought together individuals involved in multiple disciplines of information security to foster the exchange of ideas. The conference, an outgrowth of the Information Security Workshop (ISW) series, was held in Malaga, Spain, on October 1 3, 2001. Previous workshops were ISW '97 at Ishikawa, Japan; ISW '99 at Kuala Lumpur, Malaysia; and ISW 2000 at Wollongong, Australia. The General Co chairs, Javier Lopez and Eiji Okamoto, oversaw the local organization, registration, and performed many other tasks. Many individuals deserve thanks for their contribution to the success of the conference. Jose M. Troya was the Conference Chair. The General Co chairs were assisted with local arrangements by Antonio Mana, Carlos Maraval, Juan J. Ortega, Jose M. Sierra, and Miguel Soriano. This was the first year that the conference accepted electronic submissions. Many thanks to Dawn Gibson for assisting in developing and maintaining the electronic submission servers. The conference received 98 submissions of which 37 papers were accepted for presentation. These proceedings contain revised versions of the accepted papers. Revisions were not checked and the authors bear full responsibility for the contents of their papers. The Program Committee consisted of Elisa Bertino, Universita di Milano; G. R."

The third International Workshop on Information Security was held at the U- versity of Wollongong, Australia. The conference was sponsored by the Centre for Computer Security Research, University of Wollongong. The main themes of the conference were the newly emerging issues of Information Security. Mul- media copyright protection and security aspects of e-commerce were two topics that clearly re?ect the focus of the conference. Protection of the copyright of electronic documents seems to be driven by strong practical demand from the industry for new, e cient and secure solutions. Although e-commerce is already booming, it has not reached its full potential in terms of new, e cient and secure e-commerce protocols with added properties. There were 63 papers submitted to the conference. The program committee accepted 23. Of those accepted, six papers were from Australia, ve from Japan, two each from Spain, Germany and the USA, and one each from Finland and Sweden. Four papers were co-authored by international teams from Canada and China, Korea and Australia, Taiwan and Australia, and Belgium, France and Germany, respectively. Final versions of the accepted papers were gathered using computing and other resources of the Institute of Mathematics, Polish Academy of Sciences, Warsaw, Poland. We are especially grateful to Jerzy Urbanowicz and Andrzej Pokrzywa for their help during preparation of the proceedings.

WelcometoRotterdamandtotheInternationalConferenceSafecomp2000,on thereliability,safetyandsecurityofcriticalcomputerapplications. Thisalready marksthe19thyearoftheconference,showingtheundiminishedinterestthe topicelicitsfrombothacademiaandindustry. Safecomphasproventobean excellentplacetomeetandhavediscussions,andwehopethistrendcontinues thisyear. Peopleandorganisationsdependmoreandmoreonthefunctioningofc- puters. Whetherinhouseholdequipment,telecommunicationsystems,o?ce- plications,banking,peoplemovers,processcontrolormedicalsystems,theoft- embeddedcomputersubsystemsaremeanttoletthehostingsystemrealiseits intendedfunctions. Theassuranceofproperfunctioningofcomputersin- pendableapplicationsisfarfromobvious. Themillenniumstartedwiththebug andthefullendorsementoftheframeworkstandardIEC61508. Thevariety ofdependablecomputerapplicationsincreasesdaily,andsodoesthevarietyof risksrelatedtotheseapplications. Theassessmentoftheserisksthereforeneeds re?ectionandpossiblynewapproaches. Thisyear'sSafecompprovidesabroad mixofpapersontheseissues,onprogressmadeindi?erentapplicationdomains andonemergingchallenges. Oneofthespecialtopicsthisyearistransportandinfrastructure. Onewould behardpressedto?ndabetterplacetodiscussthisthaninRotterdam. The reliability,safetyandsecurityofcomputersisofprominentimportancetoRott- dam,asafewexamplesillustrate. Itsharbourdependsonthereliablefunctioning ofcontainerhandlingsystems,onthesafefunctioningofitsradarsystems,and, asofrecently,onthesafeandreliablefunctioningoftheenormousstormsurge barrieratHoekvanHolland. AnewtopicforSafecompis medicalsystems. Theseprogressivelydepend on-embedded-programmableelectronicsystems. Experienceshowsthatthe medicalworldlacksthemethodsforapplyingthesesystemssafelyandreliably. Wewelcomeagroupofpeoplereadytodiscussthistopic,andhope,bydoing so,tocontributetothis?eldofapplicationsofsafe,reliableandsecuresystems. SoftwareprocessimprovementalsorepresentsaspecialtopicofSafecomp 2000. Itprovedtobethemostfruitfulofthethreeintermsofsubmittedpapers. Thereweremanycontributionsfromahostofcountries,whichhadtobespread amongstdi?erentsessiontopics. WewishtothanktheInternationalProgramCommittee'smembers,41in total,fortheire?ortsinreviewingthepapersandfortheirvaluableadvicein organisingthisconference. Wearealsogratefulfortheircontributiontod- tributingcallsforpapersandannouncements. Withouttheirhelptheburdenof organisingthisconferencewouldhavebeenmuchgreater. VI Preface Finally,letusonceagainwelcomeyoutoRotterdam,atrulyinternational cityandhometopeopleofmanynationalities. Wehopeyoutakethetimenot onlytoenjoythisconference,butalsoto?ndyourwayaroundthecity,sinceit surelyhasmuchtoo?er. FloorKoornneef MeinevanderMeulen Table of Contents InvitedPaper TheTenMostPowerfulPrinciplesforQualityin(Softwareand) SoftwareOrganizationsforDependableSystems...1 TomGilb Veri?cationandValidation EmpiricalAssessmentofSoftwareOn-LineDiagnostics UsingFaultInjection...14 JohnNapier,JohnMayandGordonHughes Speeding-UpFaultInjectionCampaignsinVHDLModels...27 B. Parrotta,M. Rebaudengo,M. SonzaReordaandM. Violante Speci?cationandVeri?cationofaSafetyShellwithStatechartsand ExtendedTimedGraphs...37 JanvanKatwijk,HansToetenel,Abd-El-KaderSahraoui,EricAnderson andJanuszZalewski ValidationofControlSystemSpeci?cationswithAbstractPlantModels...53 WenhuiZhang AConstantPerturbationMethodforEvaluation ofStructuralDiversityinMultiversionSoftware...63 LupingChen,JohnMayandGordonHughes ExpertError:TheCaseofTrouble-ShootinginElectronics...74 DenisBesnard TheSafetyManagementofData-DrivenSafety-RelatedSystems ...86 A. G. Faulkner,P. A. Bennett,R. H. Pierce,I. H. A. Johnston andN. Storey SoftwareSupportforIncidentReportingSystems inSafety-CriticalApplications...96 ChrisJohnson SoftwareProcessImprovement ADependability-ExplicitModelfortheDevelopment ofComputingSystems...107 MohamedKaan iche,Jean-ClaudeLaprieandJean-PaulBlanquart VIII Table ofContents DerivingQuanti?edSafetyRequirementsinComplexSystems ...117 PeterA. Lindsay,JohnA. McDermidandDavidJ. Tombs ImprovingSoftwareDevelopmentbyUsing SafeObjectOrientedDevelopment:OTCD...131 XavierM'ehautandPierreMor'ere ASafetyLicensablePESforSIL4Applications...141 WolfgangA. Halang,PeterVogrinandMatja?zColnari?c SafetyandSecurityIssuesinElectricPowerIndustry ...151 ? Zdzis lawZurakowski DependabilityofComputerControlSystemsinPowerPlants ...165 Cl'audiaAlmeida,AlbertoArazo,YvesCrouzetandKaramaKanoun AMethodofAnalysisofFaultTreeswithTimeDependencies ...176 JanMagottandPawe lSkrobanek Formal Methods AFormalMethodsCaseStudy:UsingLight-WeightVDM fortheDevelopmentofaSecuritySystemModule...187 GeorgDroschl,WalterKuhn,GeraldSonneckandMichaelThuswald FormalMethods:TheProblemIsEducation...198 ThierryScheurer FormalMethodsDi?usion:PastLessonsandFutureProspects...211 R. Bloom?eld,D. Craigen,F. Koob,M. UllmannandS. Wittmann InvitedPaper SafeTech:AControlOrientedViewpoint...227 MaartenSteinbuch SafetyGuidelines,StandardsandCerti?cation DerivationofSafetyTargetsfortheRandomFailure ofProgrammableVehicleBasedSystems...240 RichardEvansandJonathanMo?ett IEC61508-ASuitableBasisfortheCerti?cation ofSafety-CriticalTransport-InfrastructureSystems??...250 DerekFowlerandPhilBennett Table of Contents IX HardwareAspects AnApproachtoSoftwareAssistedRecovery fromHardwareTransientFaultsforRealTimeSystems...264 D. BasuandR. Paramasivam ProgrammableElectronicSystemDesign&Veri?cationUtilizingDFM...275 MichelHoutermans,GeorgeApostolakis,AarnoutBrombacher andDimitriosKarydas SIMATICS7-400F/FH:Safety-RelatedProgrammableLogicController...286 AndreasSchenk SafetyAssessmentI AssessmentoftheReliabilityofFault-TolerantSoftware: ABayesianApproach...294 BevLittlewood,PeterPopovandLorenzoStrigini EstimatingDependabilityofProgrammableSystemsUsingBBNs...309 BjornAxelGran,GustavDahll,SiegfriedEisinger,EivindJ. Lund, JanGerhardNorstrom,PeterStrockaandBrittJ. Ystanes DesignforSafety ImprovementsinProcessControlDependability throughInternetSecurityTechnology...321 FerdinandJ. Dafelmair ASurveyonSafety-CriticalMulticastNetworking ...333 JamesS. PascoeandR. J. Loader InvitedPaper CausalReasoningaboutAircraftAccidents...344 PeterB. Ladkin Transport&Infrastructure ControllingRequirementsEvolution:AnAvionicsCaseStudy...361 StuartAndersonandMassimoFelici HAZOPAnalysisofFormalModels ofSafety-CriticalInteractiveSystems...

I would like to welcome all the participants to the 3rd International Conference on Information Security and Cryptology (ICISC 2000). It is sponsored by the Korea Institute of Information Security and Cryptology (KIISC) and is being held at Dongguk University in Seoul, Korea from December 8 to 9, 2000. This conference aims at providing a forum for the presentation of new results in research, development, and application in information security and cryptology. This is also intended to be a place where research information can be exchanged. The Call for Papers brought 56 papers from 15 countries and 20 papers will be presented in ve sessions. As was the case last year the review process was totally blind and the anonymity of each submission was maintained. The 22 TPC members nally selected 20 top-quality papers for presentation at ICISC 2000. I am very grateful to the TPC members who devoted much e ort and time to reading and selecting the papers. We also thank the experts who assisted the TPC in evaluating various papers and apologize for not including their names here. Moreover, I would like to thank all the authors who submitted papers to ICISC 2000 and the authors of accepted papers for their preparation of came- ready manuscripts. Last but not least, I thank my student, Joonsuk Yu, who helped me during the whole process of preparation for the conference. I look forward to your participation and hope you will nd ICISC 2000 a truly rewarding experience.

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 ...1 47 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...

This book constitutes the refereed proceedings of the Second International Conference in Cryptology in India, INDOCRYPT 2001, held in Chennai, India in December 2001. The 31 revised full papers presented together with an invited survey were carefully reviewed and selected from 77 submissions. The papers are organized in topical sections on hashing, algebraic schemes, elliptic curves, coding theory, applications, cryptanalysis, distributed cryptography, Boolean functions, digitial signatures, and shift registers.

Some years ago, businesses could choose whether to migrate to electronic commerce, however, today it seems they have no choice. Predictions indicate that companies that do not make the necessary changes will be overrun by competition and ultimately fail. Therefore, we see more and more companies undergoing tremendous transformationin order to adapt to the new business paradigm. At the same time new companies are being established. One thing these companies have in common is the increased dependency on security technology. The invention of electronic commerce has changed the role of - curity technologies from being merely a protector to being also an enabler of electronic commerce, and it is clear that the development of security techn- ogy is a key enabler in the growth and deployment of electronic commerce. This has been recognised at European level (European Union 1997e). The launch of a comprehensive EU policy in the area of security in open networksisfairlyrecentwiththeadoptionofaCommunicationoncryptog- phy inOctober 1997(EuropeanUnion1997c). A veryimportantcomplement and support to the European policy is the European Commission s contri- tion to overcometechnological barriers by giving special importance to R&D (Research and Development) activities. The SEMPER project was launched in September 1995 and was funded partly by the European Community within the Advanced Communication Technologies and Services (ACTS) speci?c research programme part of the Fourth Framework Program (1994-1998). In this book the SEMPER project team presents in a coherent, integrated, and readable form the issues - dressed, themotivationfortheworkcarriedout, andthekeyresultsobtained. SEMPER is an innovative project in several aspects."

Security is a rapidly growing area of computer science, with direct and increasing relevance to real life applications such as Internet transactions, electronic commerce, information protection, network and systems integrity, etc. This volume presents thoroughly revised versions of lectures given by leading security researchers during the IFIP WG 1.7 International School on Foundations of Security Analysis and Design, FOSAD 2000, held in Bertinoro, Italy in September. Mathematical Models of Computer Security (Peter Y.A. Ryan); The Logic of Authentication Protocols (Paul Syversen and Iliano Cervesato); Access Control: Policies, Models, and Mechanisms (Pierangela Samarati and Sabrina de Capitani di Vimercati); Security Goals: Packet Trajectories and Strand Spaces (Joshua D. Guttman); Notes on Nominal Calculi for Security and Mobility (Andrew D. Gordon); Classification of Security Properties (Riccardo Focardi and Roberto Gorrieri).

This book constitutes the refereed proceedings of the Third International Conference on Information and Communications Security, ICICS 2001, held in Xian, China in November 2001.The 56 revised full papers presented were carefully reviewed and selected from a total of 134 submissions. The complete spectrum of information and communications security is covered including theoretical foundations, secret sharing, network security, authentication and identification, Boolean functions and stream ciphers, security evaluation, digital signatures, block ciphers and public-key systems, information hiding, security protocols, and cryptanalysis.

This book constitutes the refereed proceedings of the 20th International Conference on Computer Safety, Reliability, and Security, SAFECOMP 2001, held in Budapest, Hungary, in September 2001.The 20 revised full papers presented together with three invited papers were carefully reviewed and selected. The book offers topical sections on reliability assessment and security, safety case and safety analysis, medical systems, human-machine interface, COTS - components off the shelf, testing, formal methods, and control systems.

This book constitutes the refereed proceedings of the Cryptographers' Track at RSA Conference 2001, CT-RSA 2001, in San Francisco, CA, USA in April 2001.The 33 revised full papers presented were carefully reviewed and selected from 65 submissions. The papers are organized in topical sections on new cryptosystems; RSA; symmetric cryptography; gambling and lotteries; reductions, constructions, and security proofs; flaws and attacks; implementation; multivariate cryptography; number theoretic problems; passwords and credentials; and protocols.

This book constitutes the thoroughly refereed post-proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2000, held in Worcester, MA, USA in August 2000. The 25 revised full papers presented together with two invited contributions were carefully reviewed and selected from 51 submissions. The papers are organized in topical sections on implementation of elliptic curve cryptosystems, power and timing analysis attacks, hardware implementation of block ciphers, hardware architectures, power analysis attacks, arithmetic architectures, physical security and cryptanalysis, and new schemes and algorithms.

This book constitutes the refereed proceedings of the Fourth International Workshop on Recent Advances in Intrusion Detection, RAID 2001, held in Davis, CA, USA, in October 2001.The 12 revised full papers presented were carefully reviewed and selected from a total of 55 submissions. The papers are organized in sections on logging, cooperation, anomaly detection, intrusion tolerance, legal aspects and specification-based IDS.

This book constitutes the thoroughly refereed post-proceedings of the Third International Workshop on Cryptoanalysis Hardware and Embedded Systems, CHES 2001, held in Paris, France in Mai 2001. The 31 revised full papers presented were carefully reviewed and selected from 66 submissions. The papers are organized in topical sections on side channel attacks, Rijndael hardware implementation, random number generators, elliptic curve algorithms, arithmetic architectures, cryptanalysis, embedded implementations of ciphers, and side channel attacks on elliptic curve cryptosystems.

This book constitutes the thoroughly refereed post-proceedings of the International Conference on Cryptography and Lattices, CaLC 2001, held in Providence, RI, USA in March 2001. The 14 revised full papers presented together with an overview paper were carefully reviewed and selected for inclusion in the book. All current aspects of lattices and lattice reduction in cryptography, both for cryptographic construction and cryptographic analysis, are addressed.

Although a vast literature exists on the subject of RSA and public-key cryptography, until now there has been no single source that reveals recent developments in the area at an accessible level. Acclaimed author Richard A. Mollin brings together all of the relevant information available on public-key cryptography (PKC), from RSA to the latest applications of PKC, including electronic cash, secret broadcasting, secret balloting systems, various banking and payment protocols, high security logins, smart cards, and biometrics. Moreover, he covers public-key infrastructure (PKI) and its various security applications.

Throughout the book, Mollin gives a human face to cryptography by including nearly 40 biographies of the individuals who helped develop cryptographic concepts. He includes a number of illustrative and motivating examples, as well as optional topics that go beyond the basics, such as Lenstra's elliptic curve method and the number field sieve. From history and basic concepts to future trends and emerging applications, this book provides a rigorous and detailed treatment of public-key cryptography. Accessible to anyone from the senior undergraduate to the research scientist, RSA and Public-Key Cryptography offers challenging and inspirational material for all readers.

This book covers a broader scope of Attribute-Based Encryption (ABE), from the background knowledge, to specific constructions, theoretic proofs, and applications. The goal is to provide in-depth knowledge usable for college students and researchers who want to have a comprehensive understanding of ABE schemes and novel ABE-enabled research and applications. The specific focus is to present the development of using new ABE features such as group-based access, ID-based revocation, and attributes management functions such as delegation, federation, and interoperability. These new capabilities can build a new ABE-based Attribute-Based Access Control (ABAC) solution that can incorporate data access policies and control into ciphertext. This book is also ideal for IT companies to provide them with the most recent technologies and research on how to implement data access control models for mobile and data-centric applications, where data access control does not need to rely on a fixed access control infrastructure. It's also of interested to those working in security, to enable them to have the most recent developments in data access control such as ICN and Blockchain technologies. Features Covers cryptographic background knowledge for ABE and ABAC Features various ABE constructions to achieve integrated access control capabilities Offers a comprehensive coverage of ABE-based ABAC Provides ABE applications with real-world examples Advances the ABE research to support new mobile and data-centric applications

ASIACRYPT 2000 was the sixth annual ASIACRYPT conference. It was sp- sored by the International Association for Cryptologic Research (IACR) in - operation with the Institute of Electronics, Information, and Communication Engineers (IEICE). The ?rst conference with the name ASIACRYPT took place in 1991, and the series of ASIACRYPT conferences were held in 1994, 1996, 1998, and 1999, in cooperation with IACR. ASIACRYPT 2000 was the ?rst conference in the series to be sponsored by IACR. The conference received 140 submissions (1 submission was withdrawn by the authors later), and the program committee selected 45 of these for presen- tion. Extended abstracts of the revised versions of these papers are included in these proceedings. The program also included two invited lectures by Thomas Berson (Cryptography Everywhere: IACR Distinguished Lecture) and Hideki Imai (CRYPTREC Project - Cryptographic Evaluation Project for the Japanese Electronic Government). Abstracts of these talks are included in these proce- ings. The conference program also included its traditional "rump session" of short, informal or impromptu presentations, kindly chaired by Moti Yung. Those p- sentations are not re?ected in these proceedings. The selection of the program was a challenging task as many high quality submissions were received. The program committee worked very hard to evaluate the papers with respect to quality, originality, and relevance to cryptography. I am extremely grateful to the program committee members for their en- mous investment of time and e?ort in the di?cult and delicate process of review and selection.

This book constitutes the thoroughly refereed post-workshop proceedings of the Third International Workshop on Information Hiding, IH'99, held in Dresden, Germany, in September/October 1999.The 33 revised full papers presented were carefully reviewed and selected from a total of 68 submissions. The dominating topic, dealt with in various contexts, is watermarking. The papers are organized in sections on fundamentals of steganography, paradigms and examples, beyond symmetric steganography; watermarking: proving ownership, detection and decoding, embedding techniques, new designs and applications, improving robustness, software protection; separating private and public information; and stego-engineering.

ThePKC2000conferencewasheldattheMelbourneExhibitionCentre, Victoria, Australia, January 18-20, 2000. It was the third conference in the international workshop series dedicated to practice and theory in public key cryptography. The program committee of the conference received 70 full submissions from around the world, of which 31 were selected for presentation. All submissions were reviewed by experts in the relevant areas. The program committee consisted of 19 experts in cryptography and data se- rity drawn from the international research community, these being Chin-Chen Chang (National Chung Cheng University, Taiwan), Claude Cr epeau (McGill University, Canada), Ed Dawson (Queensland University of Technology, A- tralia), Yvo Desmedt (Florida State University, USA), Hideki Imai (Co-chair, UniversityofTokyo, Japan), MarkusJakobsson(BellLabs, USA), KwangjoKim (Information and Communications University, Korea), Arjen Lenstra (Citibank, USA), TsutomuMatsumoto(YokohamaNationalUniversity, Japan), DavidN- cache (Gemplus, France), Eiji Okamoto (University of Wisconsin-Milwaukee, USA), TatsuakiOkamoto(NTTLabs, Japan), JosefPieprzyk(UniversityofW- longong, Australia), Jean-Jacques Quisquater (Universit e Catholique de L- vain, Belgium), Nigel Smart (HP Labs Bristol, UK), Vijay Varadharajan (U- versity of Western Sydney, Australia), Serge Vaudenay (Ecole Polytechnique F ed erale de Lausanne, Switzerland), Moti Yung (CertCo, USA), and Yuliang Zheng (Co-chair, Monash University, Australia). Members of the committee spent numerous hours in reviewing the submissions and providing advice and comments on the selection of paper