SPRINGER BRIEFS IN COMPUTER SCIENCE Giulia Traverso Denise Demirel Johannes Buchmann Homomorphic Signature Schemes A Survey 123 SpringerBriefs in Computer Science SeriesEditors StanZdonik,BrownUniversity,Providence,USA ShashiShekhar,UniversityofMinnesota,Minneapolis,USA JonathanKatz,UniversityofMaryland,CollegePark,USA XindongWu,UniversityofVermont,Burlington,USA LakhmiC.Jain,UniversityofSouthAustralia,Adelaide,Australia DavidPadua,UniversityofIllinoisUrbana-Champaign,Urbana,USA Xuemin(Sherman)Shen,UniversityofWaterloo,Waterloo,Canada BorkoFurht,FloridaAtlanticUniversity,BocaRaton,USA V.S.Subrahmanian,UniversityofMaryland,CollegePark,USA MartialHebert,CarnegieMellonUniversity,Pittsburgh,USA KatsushiIkeuchi,UniversityofTokyo,Tokyo,Japan BrunoSiciliano,UniversitàdiNapoliFedericoII,Napoli,Italy SushilJajodia,GeorgeMasonUniversity,Fairfax,USA NewtonLee,NewtonLeeLaboratories,LLC,Tujunga,USA Moreinformationaboutthisseriesathttp://www.springer.com/series/10028 Giulia Traverso (cid:129) Denise Demirel Johannes Buchmann Homomorphic Signature Schemes A Survey 123 GiuliaTraverso DeniseDemirel TheoretischeInformatik TheoretischeInformatik TechnischeUniversitätDarmstadt TechnischeUniversitätDarmstadt Darmstadt,Hessen,Germany Darmstadt,Hessen,Germany JohannesBuchmann TheoretischeInformatik TechnischeUniversitätDarmstadt Darmstadt,Hessen,Germany ISSN2191-5768 ISSN2191-5776 (electronic) SpringerBriefsinComputerScience ISBN978-3-319-32114-1 ISBN978-3-319-32115-8 (eBook) DOI10.1007/978-3-319-32115-8 LibraryofCongressControlNumber:2016935494 ©TheAuthor(s)2016 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAGSwitzerland Preface In the last years, there has been an increasing interest in homomorphic signature schemes. Thus, many schemes have been proposed that are suitable for a lot of different applications. In this work, we overcome the extensive state of the art by presenting a survey of the existing approaches and the properties they provide. In addition, we look into three interesting use cases for homomorphic operations on authenticated data; these are electronic voting, smart grids, and electronic health records. We discuss their requirements, show to what extent the existing solutions meettheseconditions,andhighlightpromisingdirectionsforfuturework. Homomorphic signature schemes have been initially designed to establish authentication in network coding and to address pollution attacks (see [18]). However, since they allow for computations on authenticated data, they are also a usefulprimitiveformanyotherapplications.Infact,afterJohnsonetal.introduceda formaldefinitionandapreciseframeworkforhomomorphicsignaturesin2002(see [46]),inthefollowingyears,manyschemeshavebeenpresentedanddiscussed.The firstschemesproposedonlyallowtoperformlinearcomputationsonauthenticated data(e.g.,[71,72,76],and[24]).Theseapproacheshavebeenfurtherimprovedwith respect to efficiency, security, and privacy [5–7,15,18,21,22,22,34,36,65]. In addition,tobemoreflexible,solutionshavebeendevelopedsupportingpolynomial functions [14, 23, 43], or even coming without any restrictions on the functions themselves,so-calledfullyhomomorphicsignatureschemes[19,41].However,all thesesolutionsassumethateachinputsignaturehasbeengeneratedusingthesame privatekey.Toovercomethisrestriction,thehomomorphicpropertyhasbeenadded to the aggregate signature schemes [45, 74] allowing for operations on signatures generatedusingevendifferentsecret-publickeypairs. In this work, we start by providing a formal definition of these four types of homomorphic signature schemes. First, the passage from the digital signature schemes to the homomorphic ones is formally described, where the novelties introduced by the homomorphic property itself are highlighted. Afterward, it is described how to obtain the linearly homomorphic signature schemes from the merely homomorphic ones. And then, starting from the linearly homomorphic signature schemes, it is shown how to derive the schemes supporting polynomial v vi Preface functions and how to define the fully homomorphic signature schemes. Finally, schemes that allow computations on signatures generated using different secret- publickeypairsareformallydescribed. Up to our knowledge, this survey is the first such work providing both a description of each single homomorphic signature scheme and a description of the whole general framework in a methodical and didactic approach. Indeed the survey proposed in [73] is not up to date, while in [20] the existing homomorphic signature schemes are just listed, without any deeper discussions. Furthermore, in this survey, we also discuss the possible use cases electronic voting, smart grids, and electronic health records. For each use case, concrete examples of how improvementscanbeachievedbytheusageofhomomorphicsignatureschemesare provided, together with the definition of the minimal requirements these schemes shouldfulfill.Furthermore,itisshownwhichofthecurrentlyexistinghomomorphic signatureschemesaresuitableforwhichoftheusecasesinquestion.Whenthatis notthecase,directionsforfutureworksareproposed. In Chap.1, the definition of general digital signature schemes is recalled, and the formal description of the homomorphic signature schemes is provided. Chapter 2 provides a description of the linearly homomorphic signature schemes, thehomomorphicsignatureschemesforpolynomialfunctions,thefullyhomomor- phic signature schemes, and the homomorphic aggregate signature schemes. In Chap.3, interesting properties of homomorphic signature schemes are discussed. The description of each of the currently existing homomorphic signature scheme and the properties they provide follow in Chap.4. In Chap.5, the usage of homo- morphic signature schemes for each of the aforementioned use cases is presented. Finally,inChap.6,aconclusionisgivenandpossibledirectionsforfutureworkare shown. Darmstadt,Germany GiuliaTraverso February2016 DeniseDemirel JohannesBuchmann Acknowledgments Thisworkhasbeenco-fundedbytheEuropeanUnion’sHorizon2020researchand innovationprogramundergrantagreementno.644962.Inaddition,ithasreceived funding from the DFG as part of project Long-Term Secure Archiving Within the CRC1119CROSSING.WewouldliketothankalsoLucasShabhüser,NinaBindel, DanielSlamanig,andDavidDerlerforthenicediscussions. vii Contents 1 FromDigitaltoHomomorphicSignatureSchemes....................... 1 1.1 DigitalSignatures........................................................ 1 1.2 DigitalSignatureSchemesSecurityDefinition......................... 2 1.2.1 Known-MessageAttack......................................... 3 1.2.2 Chosen-MessageAttack......................................... 4 1.2.3 AdaptiveChosen-MessageAttack.............................. 5 1.3 HomomorphicSignatureSchemes...................................... 6 1.4 HomomorphicSignatureSchemesSecurityDefinition ................ 9 2 HomomorphicSignatureSchemes.......................................... 11 2.1 HomomorphicSignatureSchemesfortheSingle-UserScenario...... 11 2.1.1 LinearlyHomomorphicSignatureSchemes.................... 11 2.1.2 HomomorphicSignatureSchemesforPolynomial Functions......................................................... 13 2.1.3 FullyHomomorphicSignatures................................. 14 2.2 HomomorphicSignatureSchemesfortheMulti-UsersScenario...... 14 2.2.1 MultipleSourcesHomomorphicSignatureSchemes.......... 15 2.2.2 HomomorphicAggregateSignatureSchemes.................. 17 3 EvaluationofHomomorphicSignatureSchemes.......................... 23 3.1 HardnessAssumptions................................................... 23 3.1.1 BilinearGroups.................................................. 23 3.1.2 RSA .............................................................. 26 3.1.3 Lattices........................................................... 27 3.2 EfficiencyandSize....................................................... 29 3.3 Security................................................................... 30 3.3.1 WeakAdversary ................................................. 30 3.3.2 StrongAdversary ................................................ 31 3.4 Privacy.................................................................... 32 3.5 RandomOracleModelvs.StandardModel ............................ 33 ix