Lecture Notes in Computer Science 5671 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Hovav Shacham Brent Waters (Eds.) Pairing-Based Cryptography – Pairing 2009 Third International Conference Palo Alto, CA, USA, August 12-14, 2009 Proceedings 1 3 VolumeEditors HovavShacham UniversityofCaliforniaatSanDiego DepartmentofComputerScienceandEngineering 9500GilmanDrive,MC0404 LaJolla,CA92093-0404,USA E-mail:[email protected] BrentWaters UniversityofTexasatAustin DepartmentofComputerScience 1UniversityStationC0500,TaylorHall2.124 Austin,TX78712-1188,USA E-mail:[email protected] LibraryofCongressControlNumber:2009930958 CRSubjectClassification(1998):E.3,D.4.6,F.2.2,G.2,K.6.5 LNCSSublibrary:SL4–SecurityandCryptology ISSN 0302-9743 ISBN-10 3-642-03297-4SpringerBerlinHeidelbergNewYork ISBN-13 978-3-642-03297-4SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. springer.com ©Springer-VerlagBerlinHeidelberg2009 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:12723874 06/3180 543210 Preface Pairing 2009, the Third International Conference on Pairing-Based Cryptogra- phy, was held at Stanford University in Palo Alto during August 12–14, 2009. The conference was sponsored by Voltage Security and Microsoft Corporation. TerenceSpiesservedasGeneralChairoftheConferenceandwehadtheprivilege of serving as ProgramCo-chairs. Theconferencereceived38submissions.Thesewerereviewedbyacommittee of23members.Thecommitteehadathree-weekindividualreviewphasefollowed by three weeks of discussion. After careful deliberation, the committee chose 16 papers for the Pairing 2009 conference. Detailed reviews were given to the authors, and the authors were given three weeks to submit the final version. These final versions were not subject to external review and the authors bear full responsibility for their contents. We are delighted to have had three invited speakers for Pairing2009.Victor Miller spoke on the origins of pairing-basedcryptography.His talk was comple- mentedbyTanjaLange’s,whocoveredthe evolutionofthe mathematicsbehind pairings and shared recent results. Finally, Amit Sahai spoke on his work (with Jens Groth and Rafi Ostrovksy)realizing non-interactivezero knowledge proofs from pairings. This work has been highly influential and multiple papers ac- cepted at this conference built upon it. In addition, there was a “Hot Topics” session at this conference where we asked several researchers to give 10-minute presentations of recent results. We would like to thank everyone who contributed to the conference. First, thankstothemembersofourProgramCommitteefortheirexcellentreviews,the difficult decisions they made in a short time, and their conscientious, thorough shepherding.Second,thanksto the PairingConferenceSteering Committee and the Chairs of previous Pairing conferences and workshops. We would like to extend a particular thanks to Steven Galbraith and Kenny Paterson, Program ChairsofPairing2008,whoseexperienceandadvicewereinvaluabletousinour planning of this conference. Third, we would like to thank Shai Halevi, whose wonderful Web Submission and Review Software we used and who hosted and administeredthesubmissionandreviewsiteforusontheIACR’sservers.Fourth, we are grateful for Voltage Security and Microsoft for their generous support. Finally, we are especially indebted to Terence Spies for his service as General Chair. Without him the conference would not have been possible. August 2009 Hovav Shacham Brent Waters Pairing 2009 The Third International Conference on Pairing-BasedCryptography Stanford, California August 12–14,2009 Sponsored by Voltage Security and Microsoft General Chair Terence Spies Voltage Security Program Chairs Hovav Shacham UC San Diego, USA Brent Waters UT Austin, USA Program Committee Michel Abdalla E´cole Normale Sup´erieure, France Paulo Barreto University of Sa˜o Paulo, Brazil Xavier Boyen Stanford, USA Melissa Chase Microsoft Research, USA David Mandell Freeman CWI; Universiteit Leiden, The Netherlands Steven Galbraith Royal Holloway,University of London, UK Pierrick Gaudry CNRS, INRIA, Nancy Universit´e, France Matthew Green Johns Hopkins, USA Jens Groth University College London, UK Florian Hess TU Berlin, Germany Tanja Lange TU Eindhoven, The Netherlands Kristin Lauter Microsoft Research, USA Gregory Neven IBMZurichResearchLaboratory,Switzerland Tatsuaki Okamoto NTT, Japan Dan Page University of Bristol, UK Kenny Paterson Royal Holloway,University of London, UK Michael Scott Dublin City University, Ireland Hovav Shacham UC San Diego, USA Elaine Shi PARC, USA Nigel Smart University of Bristol, UK Tsuyoshi Takagi Future University Hakodate, Japan Fr´e Vercauteren KU Leuven, Belgium Brent Waters UT Austin, USA VIII Organization External Reviewers John Bethencourt Atsuko Miyaji Katsuyuki Takashima S´ebastien Canard Peter Montgomery Damien Vergnaud Scott E. Coull Yasuyuki Nogami Ali Zandi Yuto Kawahara Pascal Paillier Benoˆıt Libert Emily Shen Mark Manulis Masaaki Shirase Table of Contents Signature Security Boneh-BoyenSignatures and the Strong Diffie-Hellman Problem ....... 1 David Jao and Kayo Yoshida SecurityofVerifiablyEncryptedSignaturesandaConstructionwithout Random Oracles ................................................ 17 Markus Ru¨ckert and Dominique Schro¨der Multisignatures as Secure as the Diffie-Hellman Problem in the Plain Public-Key Model................................................ 35 Duc-Phong Le, Alexis Bonnecaze, and Alban Gabillon Curves On the Security of Pairing-Friendly Abelian Varieties over Non-prime Fields .......................................................... 52 Naomi Benger, Manuel Charlemagne, and David Mandell Freeman Generating Pairing-Friendly Curves with the CM Equation of Degree 1........................................................ 66 Hyang-Sook Lee and Cheol-Min Park Pairing Computation On the Final Exponentiation for Calculating Pairings on Ordinary Elliptic Curves .................................................. 78 Michael Scott, Naomi Benger, Manuel Charlemagne, Luis J. Dominguez Perez, and Ezekiel J. Kachisa Faster Pairings on Special Weierstrass Curves ....................... 89 Craig Costello, Huseyin Hisil, Colin Boyd, Juan Gonzalez Nieto, and Kenneth Koon-Ho Wong Fast Hashing to G on Pairing-Friendly Curves ...................... 102 2 Michael Scott, Naomi Benger, Manuel Charlemagne, Luis J. Dominguez Perez, and Ezekiel J. Kachisa NIZKs and Applications Compact E-Cash and Simulatable VRFs Revisited ................... 114 Mira Belenkiy, Melissa Chase, Markulf Kohlweiss, and Anna Lysyanskaya X Table of Contents Proofs on Encrypted Values in Bilinear Groups and an Application to Anonymity of Signatures.......................................... 132 Georg Fuchsbauer and David Pointcheval Group Signatures Identity Based Group Signatures from Hierarchical Identity-Based Encryption...................................................... 150 Nigel P. Smart and Bogdan Warinschi Forward-Secure Group Signatures from Pairings ..................... 171 Toru Nakanishi, Yuta Hira, and Nobuo Funabiki Efficient Traceable Signatures in the Standard Model................. 187 Benoˆıt Libert and Moti Yung Protocols Strongly Secure Certificateless Key Agreement....................... 206 Georg Lippold, Colin Boyd, and Juan Gonzalez Nieto Universally Composable Adaptive Priced Oblivious Transfer........... 231 Alfredo Rial, Markulf Kohlweiss, and Bart Preneel Conjunctive Broadcast and Attribute-Based Encryption .............. 248 Nuttapong Attrapadung and Hideki Imai Author Index.................................................. 267 Boneh-Boyen Signatures and the Strong Diffie-Hellman Problem David Jao and Kayo Yoshida(cid:2) Department of Combinatorics and Optimization University of Waterloo, Waterloo ON,N2L 3G1, Canada {djao,k2yoshid}@ecc.math.uwaterloo.ca Abstract. The Boneh-Boyensignature schemeis apairing based short signature scheme which is provably secure in the standard model under theq-StrongDiffie-Hellmanassumption.Inthispaper,weprovethecon- verse of this statement, and show that forging Boneh-Boyen signatures is actually equivalent to solving the q-Strong Diffie-Hellman problem. Using this equivalence, we exhibit an algorithm which, on the vast ma- jority of pairing-friendly curves, recovers Boneh-Boyen private keys in O(p25+ε)time,usingO(p15+ε)signaturequeries.Wepresentimplementa- tionresultscomparingtheperformanceofouralgorithm andtraditional discrete logarithm algorithms such as Pollard’s lambda algorithm and Pollard’s rho algorithm. We also discuss some possible countermeasures and strategies for mitigating the impact of these findings. 1 Introduction Theq-SDHassumptionwasproposedbyBonehandBoyen[5,6]asatooltoassist in the security analysis of the Boneh-Boyenshort signature scheme. Versions of thisassumptionarealsousedinMitsunarietal.[19],DodisandYampolskiy[12], andintheBoneh-BoyenIBEscheme[4].ThesurveyarticleofBoyen[7]liststhe q-SDH assumption as one of the first in a family of new assumptions that have appeared in the context of pairing-basedcryptography,and the first of these to be analyzed in the generic group model. Prior to this work, no equivalence was known between the security of the q- SDH assumption and the security of the Boneh-Boyensignature scheme. Boneh andBoyen[5,6]provideasecurityreductionwitharunningtimeofΘ(q2),butit only goes in one direction: namely, if the q-SDH assumptionholds, then Boneh- Boyen signatures are unforgeable. There are two reasons why one might desire to prove the converse result. One reason is practical: Cheon [10(cid:2)] has sh√own that, in groups of size p, the q-SDH problem can be solved in O( p/d+ d) √ exponentiations, instead of the O( p) operations required for discrete log, for anydivisord≤q ofp−1(a similarresultholds forp+1).Knowingthatq-SDH andBoneh-BoyenareequivalentthusallowsonetoforgeBoneh-Boyensignatures infasterthansquareroottime;inourcasethisispossibleviaaknownorchosen (cid:3) The authors were partially supported byNSERC. H.ShachamandB.Waters(Eds.):Pairing2009,LNCS5671,pp.1–16,2009. (cid:2)c Springer-VerlagBerlinHeidelberg2009