Public Key Cryptography

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...115 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...