Laila El Aimani Verifi able Composition of Signature and Encryption A Comprehensive Study of the Design Paradigms Verifiable Composition of Signature and Encryption Laila El Aimani Verifiable Composition of Signature and Encryption A Comprehensive Study of the Design Paradigms 123 LailaElAimani ÉcoleNationaledesSciencesAppliquéesdeSafi CadiAyyadUniversity Safi,Morocco ISBN978-3-319-68111-5 ISBN978-3-319-68112-2 (eBook) https://doi.org/10.1007/978-3-319-68112-2 LibraryofCongressControlNumber:2017953945 ©SpringerInternationalPublishingAG2017 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.Thepublisherremainsneutralwithregardtojurisdictional claimsinpublishedmapsandinstitutionalaffiliations. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Tomyfamily Preface Scope Cryptographicmechanismsthatrequirethefunctionalitiesofbothsignature andencryptionarebecomingnowadaysincreasinglyimportant. Consider for example the case of interorganizational electronic documents; digital signatures on these documents are indispensable to resolve disputes as they ensure integrity and authenticity of the underlying messages; however, self- authentication of the signatures will make the messages vulnerable to industrial spy or extortionist. Therefore, it is imperative to control the signature verification by applying for instance an encryption layer that obscures the signatures and makes them opaque. Also, a secure email application requires signature and encryption simultaneously to guarantee confidentiality, integrity, and authenticity oftheexchangedemails. Verifiability is an important feature in those mechanisms. In fact, it can be applicable in filtering out spams in an email application; the spam filter should be abletocheckthevalidityoftheencryptedemailwithoutdecryptingit.Besides,the receiver that decrypts the email might be compelled, for instance to resolve later disputes,toprovethatthesenderisindeedtheauthorofagivenmessage.Likewise, theauthoroftheopaquesignaturemightneedtoproveitsvaliditywithrespecttoa givenmessage,ortodelegatethistasktoathirdparty. This Book’s Objectives This book attempts to give a thorough treatment of the celebratedcompositionsofsignatureandencryptionthatallowforgoodverifiability, i.e., possibility to efficiently prove properties about the encrypted data. The study isprovidedinthecontextoftwocryptographicprimitives:(1)designatedconfirmer signatures, an opaque signature which was introduced to control the proliferation of certified copies of documents, and (2) signcryption, a primitive that offers simultaneouslyandefficientlyprivacyandauthenticity. The choice of the case-study primitives is motivated by the need to have a representativeofprimitivesthatrequirebothconfidentialityandauthenticityofthe data, and a representative of opaque signatures which obfuscate the authenticity of the signed data while disclosing the latter. The hope is to be able to extend vii viii Preface thepresent studytocover theplethora ofcryptographic mechanisms thatuseboth signatureandencryption,andneedgoodverifiability. Insteadofgivingacompendiumofresultsaboutthestudiedprimitives,Itakean instructive approach to first analyze and explain the shortcomings of the existing paradigms used to build the primitives, then proceed to the exposition of the efficient variants while giving the reader understanding and appreciation of the design methodology. Moreover, I endeavor to gradually supplement and reinforce thesecuritymodelinwhichtheprimitivesarebeinganalyzed;thegoalistoprovide flexibledesignoptionsaccordingtotherequiredsecurity. Audience Thebookisaimedatthefollowingaudiences. • Researchers in cryptology/privacy. These readers will find a single-point refer- ence book which gives a sound and rigorous treatment of the existing compo- sitions of signature and encryption found in a great number of cryptographic and privacy-preserving mechanisms. Such a book can help this audience enter quickly into and master this vast area of study. It also presents an important literature survey material which can help them find further literature and consequentlyshapetheirownresearchtopics. • Graduate and PhD students beginning their research in cryptology and infor- mation security. These readers will find in this monograph a suitable cut-down set of many properly interwoven topics that form the basic pillars of modern cryptography;tonamebutafew:digitalsignatures,(tag-based)encryption,(non) interactiveproofs,zero-knowledge,(meta)reductions. • Security engineers in high-tech companies responsible for the design and developmentofcryptographicandprivacy-preservingsolutions.Infact,thebook providesdesignprinciplesandguidelinesforcertaincryptographicmechanisms in a pedagogical manner that allows to easily extend the study to further mechanisms.Itconstitutesthenasuitableself-teachingtextforthispopulationin theareasubjecttothestudy. Content The book is organized into four parts. There is a tight continuity from one part to the next to ensure a quick comprehension of the material. Thus, Part I (Chaps.1 and 2) gives the necessary background in the theoretical foundations of modern cryptography, including the definition of the case-study primitives. Part II (Chaps.3 and 4) and Part III (Chaps.5 and 6) cover the existing compositions of signature and encryption, namely Sign_then_Encrypt (StE)andCommit_then_Encrypt_and_Sign(CtEaS)includingthespecialinstance Encrypt_then_Sign (EtS). Both parts start with a close scrutiny of the mentioned paradigmsbeforeputtingforwardthemoreefficientnewanalogs.PartIV(Chaps.7– 9)buildsfromtheworkdevelopedinthepreviouspartstopropoundnewparadigms that respond to stronger security requirements without compromising efficiency. Finally,wesummarizeinChap.10theconclusionstobedrawnfromourstudy. Preface ix Acknowledgments IdevelopedmostresultspresentedinthisbookduringmyPhDandmypostdocat the University of Bonn and Technicolor respectively. It is a pleasure to thank my PhD supervisor Joachim von zur Gathen for his invaluable support and feedback duringmystudies.AspecialnoteofthanksgotoDamienVergnaudformakingme discovercryptographicprotocolsandforhissubstantialhelpduringtheearlystages of my PhD. I would also like to express my deep gratitude to my postdoc mentor MarcJoyeforhisgeneroussupportandcountlesssuggestionstoimprovemyresults. MyPhDreviewerKennyPatersondeservesspecialmentionforreadingmythesis, apreliminaryversionofthepresentedresults,inexcruciatingdetailandgivingme constructive comments thatgreatlyimproved theresultsandinspiredmetoderive new ones. I benefited from collaboration/correspondence with many researchers; I wish to thank all my colleagues and coauthors for precious discussions which wereagreatsourceofinspirationwhilewritingthistext.IamalsogratefultoJorge NakaharaJr.forencouragingmetoturnmyresultsintoabookandforhisexcellent cooperation and availability throughout the edition process. Last but not least, I wishtoexpressmyprofoundgratitudetomyfamilyforconstantunderstandingand endless support over the years. I am also indebted to my institute ESTS at Cadi Ayyad University for providing a nice working environment for completing this work. Safi,Morocco LailaElAimani July2017 Contents PartI Background 1 Preliminaries................................................................ 3 1.1 CryptographicPrimitives.............................................. 3 1.1.1 DigitalSignatures ............................................. 3 1.1.2 Public-KeyEncryption(PKE)................................ 6 1.1.3 Key/DataEncapsulationMechanisms........................ 10 1.1.4 Tag-BasedEncryption(TBE)................................. 12 1.1.5 CommitmentSchemes ........................................ 14 1.2 Number-TheoreticProblems.......................................... 16 1.2.1 Factoring-RelatedProblems .................................. 16 1.2.2 Discrete-Log-RelatedProblems .............................. 17 1.3 ReductionistSecurity.................................................. 20 1.3.1 CryptographicReductions .................................... 20 1.3.2 ProofModels .................................................. 22 1.3.3 Meta-reductionsinCryptography ............................ 23 1.4 CryptographicProofSystems......................................... 24 1.4.1 InteractiveProofs.............................................. 24 1.4.2 Zero-Knowledge(ZK) ........................................ 25 1.4.3 †Protocols.................................................... 27 1.4.4 Non-interactiveProofs ........................................ 28 References.................................................................... 29 2 Case-StudyPrimitives...................................................... 31 2.1 ConvertibleDesignated-ConfirmerSignatures(CDCS) ............. 31 2.1.1 Motivation ..................................................... 31 2.1.2 Syntax.......................................................... 32 2.1.3 SecurityModelforCDCS .................................... 33 xi xii Contents 2.2 Signcryption ........................................................... 39 2.2.1 MotivationandChallenges.................................... 39 2.2.2 Syntax.......................................................... 41 2.2.3 SecurityModel ................................................ 42 References.................................................................... 43 PartII The“Sign_then_Encrypt”(StE)Paradigm 3 AnalysisofStE.............................................................. 49 3.1 StEforConfirmerSignatures ......................................... 49 3.1.1 TheStEParadigm............................................. 49 3.1.2 OtherVariants ................................................. 50 3.2 TheExactUnforgeabilityofStEConstructions...................... 52 3.2.1 RoadmapfortheRestoftheChapter......................... 53 3.3 ABreachinInvisibilitywithHomomorphicEncryption............ 53 3.4 ImpossibilityResultsforKey-PreservingReductions ............... 54 3.4.1 InsufficiencyofOW-CCASecureEncryption............... 55 3.4.2 InsufficiencyofNM-CPASecureEncryption................ 56 3.4.3 PuttingAllTogether........................................... 56 3.5 ExtensiontoArbitraryReductions.................................... 57 3.6 AnalysisofDamgård-Pedersen’sUndeniableSignatures ........... 60 3.7 SufficiencyofIND-PCASecureEncryption......................... 62 References.................................................................... 64 4 AnEfficientVariantofStE................................................ 67 4.1 TheNewStE........................................................... 67 4.1.1 Construction................................................... 67 4.1.2 SecurityAnalysis.............................................. 69 4.2 PracticalRealizations.................................................. 72 4.2.1 TheClassSofSignatures..................................... 73 4.2.2 TheClassEofEncryptionSchemes ......................... 74 4.2.3 Confirmation/DenialProtocols ............................... 76 4.3 FurtherEnhancements................................................. 78 4.3.1 ReducingtheSoundnessError................................ 78 4.3.2 OnlineNon-transferability.................................... 79 4.4 PerformanceoftheNewStE.......................................... 80 References.................................................................... 81 PartIII The “Commit_then_Encrypt_and_Sign” (CtEaS) Paradigm 5 AnalysisofCtEaS........................................................... 85 5.1 CtEaSforConfirmerSignatures ...................................... 85 5.2 TheExactInvisibilityofCtEaS....................................... 87 5.2.1 ImpossibilityResults.......................................... 87 5.2.2 SufficiencyofIND-PCASecureEncryption................. 89 References.................................................................... 91