Public Key Cryptography

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(UN