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

Encryption Schemes.- New Semantically Secure Public-Key Cryptosystems from the RSA-Primitive.- Optimal Chosen-Ciphertext Secure Encryption of Arbitrary-Length Messages.- On Sufficient Randomness for Secure Public-Key Cryptosystems.- Multi-recipient Public-Key Encryption with Shortened Ciphertext.- Signature Schemes.- Efficient and Unconditionally Secure Digital Signatures and a Security Analysis of a Multireceiver Authentication Code.- Formal Proofs for the Security of Signcryption.- A Provably Secure Restrictive Partially Blind Signature Scheme.- Protocols I.- M + 1-st Price Auction Using Homomorphic Encryption.- Client/Server Tradeoffs for Online Elections.- Self-tallying Elections and Perfect Ballot Secrecy.- Protocols II.- Efficient 1-Out-n Oblivious Transfer Schemes.- Linear Code Implies Public-Key Traitor Tracing.- Design and Security Analysis of Anonymous Group Identification Protocols.- On the Security of the Threshold Scheme Based on the Chinese Remainder Theorem.- Cryptanalysis.- Solving Underdefined Systems of Multivariate Quadratic Equations.- Selective Forgery of RSA Signatures with Fixed-Pattern Padding.- New Chosen-Plaintext Attacks on the One-Wayness of the Modified McEliece PKC Proposed at Asiacrypt 2000.- Side Channels.- SPA-Based Adaptive Chosen-Ciphertext Attack on RSA Implementation.- A Combined Timing and Power Attack.- A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks.- Invited Talk.- New European Schemes for Signature, Integrity and Encryption (NESSIE): A Status Report.- ECC Implementations.- An Improved Method of Multiplication on Certain Elliptic Curves.- An Alternate Decomposition of an Integer for Faster Point Multiplication on Certain Elliptic Curves.- Weierstraß Elliptic Curves and Side-Channel Attacks.- Applications.- One-Way Cross-Trees and Their Applications.- RSA Key Generation with Verifiable Randomness.- New Minimal Modified Radix-r Representation with Applications to Smart Cards.