NEW PARADIGMS IN SIGNATURE SCHEMES A DISSERTATION SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Hovav Shacham December 2005 UMI Number: 3197508 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion.
® UMI UMI Microform 3197508 Copyright 2006 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.
Box 1346 Ann Arbor, MI 48106-1346 © Copyright by Hovav Shacham 2006 All Rights Reserved 1 I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. ẻ nA - Dan Boneh Principal Adviser I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. đÁn Mitchell I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. a al dy = Rajeev Motwani Approved for the University Committee on Graduate Studies.
11 Abstract Digital signatures provide authenticity and nonrepudiation. They are a standard crypto- graphic primitive with many applications in higher-level protocols. Groups featuring a com- putable bilinear map are particularly well suited for signature-related primitives. For some signature variants the only construction known uses bilinear maps.
Where constructions based on, e., RSA are known, bilinear-map-based constructions are simpler, more efficient, and yield shorter signatures. We describe several constructions that support this claim. First, we present the Boneh-Lynn-Shacham (BLS) short signature scheme. BLS signa- tures with 1024-bit security are 160 bits long, the shortest of any scheme based on standard assumptions.
Second, we present Boneh-Gentry-Lynn-Shacham (BGLS) aggregate signatures. In an aggregate signature scheme it is possible to combine n signatures on n distinct messages from n distinct users into a single aggregate that provides nonrepudiation for all of them. BGLS aggregates are 160 bits long, regardless of how many signatures are aggregated. No construction is known for aggregate signatures that does not employ bilinear maps.
BGLS aggregates give rise to verifiably encrypted signatures, a signature variant with applications in contract signing. we present Boneh-Boyen-Shacham (BBS) group signatures. Group signatures provide anonymity for signers. Any member of the group can sign messages, but the re- sulting signature keeps the signer’s identity secret.
Only the group manager can trace the signature, undoing its anonymity, using a special trapdoor. BBS group signatures are 1443 bits long, shorter than any previous scheme by an order of magnitude. The signing operation is also an order of magnitude more efficient than in previous schemes. Finally, we consider variants and extensions of the BBS group signature scheme, in- cluding a group signature with a novel revocation mechanism that we call verifier-local revocation (VLR).
In a VLR group signature, messages announcing the revocation of some 1V users need only be processed by the verifiers; the signers are stateless. We present the Boneh-Shacham VLR group signature scheme, which has signatures even shorter than in BBS. Acknowledgments This thesis is dedicated to Helen Vincent, Meraud Grant Ferguson, and the memory of Michael Gearin-Tosh. This thesis would have been impossible without the support and mentoring of my advisor, Dan Boneh and the Applied Crypto Group at Stanford.
I have had helpful discussions and received comments and suggestions from many people, a non-exhaustive list of whom includes: Paulo Barreto, Stefan Bechtold, Mihir Bellare, Alexandra Boldyreva, Xavier Boyen, Ernie Brickell, Jan Camenisch, Liqun Chen, Cynthia Dwork, Steven Galbraith, Stanistaw Jarecki, Craig Gentry, Eu-Jin Goh, Susan Hohenberger, Yoshi Kohno, Caroline Kudla, Anna Lysyanskaya, Ilva Mironov, Nagendra Modadugu, Moni Naor, Kenny Paterson, Samuel Pepys, Zulfikar Ramzan, Eric Rescorla, Leonid Reyzin, Victor Shoup, Alice Silverberg, Nigel Smart, Martijn Stam, and Brent Waters, as well as the anonymous referees who reviewed the papers that make up the thesis. I'd like to thank the Crom Contingent — Cullen Jennings, Nagendra Modadugu, Eric Rescorla, Terence Spies, and Steve and everyone at Flex-lt; and C. better halves Lisa Dusseault and Wendy Spies. | I would, finally, like to thank my friends Susan Rea, Joy Su, Mike Sawka, Rosina Lozano, and, especially, Nick Vossbrink — without whom this thesis would doubtless not have come out when it did.
vi Contents Abstract iv Acknowledgments vi 1 Introduction 1. 0 cv cv kg v v.v V v va (oN) 2 Mathematical Background HFoàe 2. 2 g gà ng kg kg va 2.2 The Bilinear Map. c c c eee eee T~OCD@ỉIo 2.
Quà va kg UY vi Và xa 2.2 Complexity ÄssumptÌiOn§S.1 '- Computational and Decisional co-Difie Hellman. The Strong Diffie-Hellman Assumption .3 The Decision Linear Diffie-Hellman Assumption .4 Implications of DDH Hardness on G; .3 Elliptic Curves and Bilinear Maps .1 Notation and Background .2 Intractability of co-CDH on (Gi,G2).3 Hashing onto elliptic curves. ee ee ee 2.5 The bad news.00002 2 ee vii 3 Short Signatures 17 3.2 Signature Security Delnitions.38 Short Signatures based on CDH.4 Short Signatures based on SDH.1 Proof of Security 6.2 A BB Variant Secure without Random Oracles. 29 Signature Variants and Extensions 30 4.
kg kg va 30 4.3 Multisignatures and Batch Signature Verifcatlon. HH gà kg 33 4.1 Aggregate Signature 2efinitions.2 Aggregate Signatures from Bilinear Maps.5 Verifiably Encrypted SignatUres.1 Verifiably Encrypted Signature Definitions. ch kg na 4.3 Verifiably Encrypted Signatures via Aggregation .4 Verifiably-Encrypted Signatures from Bilinear Maps .5 Proofs of Security .6 Observations on Verifiably Encrypted Signatures .6 Conclusions and Open Problems. eee ee eee BH) Sequential Aggregate Signatures from Trapdoor Permutations 56 5.
kg cv k k k v KV ky 06 5. ‹ c c c k HH nu cv cv ga cv cv v kg VN cv V kh kg 57 5.1 Trapdoor One-Way Permutations.2 Certified Trapdoor Permutatlons.3 Claw-Free Permutations, Homomorphic Trapdoor Permutatlons.4 Full-Domain Signatures 2.3 Sequential Aggregate Signatures 2.4 Sequential Aggregates from Trapdoor Permutations.v k kg k KV ổn.5 Aggregating with RSA.1 Concrete Proposals for Sequential Aggregates with RSA.2 A Zero-Knowledge Protocol for SDH .3 Short Group Signatures from SDH.4 BBS Group Signature Security ©. ee 93 7 Group Signature Variants and Extensions 94 7. gà gà KV xa 94 7.2 Strong Exculpability for BBS.3 Revocation for BBS using Accumulators .4 Verifier-Local Revocation.
cu cà kg k Na sa 99 7.2 Short VLR Group Signatures from SDH.4 Proof of Security. cạn g v kg kg va 109 7.5 Efficient Revocation for BS Signatures.7 Strong Exculpability for BS.5 Conclusions and Open Problems. 0055 0 0G 118 Bibliography 119 1X List of Tables 2.1 Suitable supersingular elliptic curves with &=Ö.2 Suitable MNT curves. Suitable Barreto-Naehrig curves Chapter 1 Introduction In a digital signature scheme, Alice uses her private key to sign a message of her choice.
This procedure creates a signature, a short string that binds Alice to the message and the message to her. Anyone who has Alice’s public key, the signature, and the message can verify that the signature is valid, i., was produced by Alice on the message at hand. No one but Alice can generate a signature on any message that verifies as valid under Alice’s public key. Digital signatures thus provide authenticity and integrity.
That is, a signature by Alice on a message demonstrates that it was Alice who signed (and, therefore, intended to send) that message; and that the message is exactly the message sent by Alice, and was not tampered with. In a legal setting, they are sometimes said to provide nonrepudiation; however, this term is not well defined [77]. Signatures are a standard cryptographic primitive with many applications in higher-level protocols. Groups featuring a computable bilinear map are particularly well suited for signature-related primitives.
For some signature variants the only construction known is based on bilinear maps. Where constructions based on, e., RSA are known, bilinear-map-based constructions are simpler, more efficient, and yield shorter signatures. In this thesis, we describe several constructions that support the claim above. First, we consider Boneh-Lynn-Shacham (BLS) and Boneh-Boyen short signatures.
INTRODUCTION 2 signatures with security comparable to 1024-bit RSA are 160 bits long, the shortest of any scheme based on standard assumptions. BB signatures can be as short as BLS or (in a variant with longer signatures) can be proved secure without random oracle. Next, we present several extension and variants of BLS signatures. Amongst these is the Boneh-Gentry-Lynn-Shacham (BGLS) aggregate signature scheme.
In an aggregate signature scheme, it is possible, given n signatures on n distinct messages from n distinct users, to aggregate all these signatures into a single short signature. This single aggregate suffices to convince a verifier that the the users did indeed sign their respective messages. BGLS aggregates are based on BLS signatures and are 160 bits long, regardless of how many signatures are aggregated. No construction is known for aggregate signatures that does not employ bilinear maps.
We also show that BGLS aggregates give rise to verifiably encrypted signatures, a sig- nature variant with applications in contract signing. In a digression, we show how one can construct sequential aggregate signatures based only on the existence of trapdoor permutations. Sequential aggregate signatures is variant of aggregate signatures in which signing-and-aggregation is a single operation, in which each signer adds her signature to the aggregate signature of all the signers before her. Next, we present the Boneh-Boyen-Shacham (BBS) group signature scheme.
Group signatures provide anonymity for signers. Any member of the group can sign messages, but the resulting signature keeps the identity of the signer secret. In some systems there is a third party that can trace the signature, or undo its anonymity, using a special trapdoor. BBS group signatures with security comparable to 1024-bit RSA are 1443 bits long, shorter than any previous scheme by an order of magnitude.
The signing operation is also an order of magnitude more efficient than in previous schemes. Finally, we consider variants and extensions of the BBS group signature scheme, in- cluding a group signature with a novel revocation mechanism that we call verifier-local revocation (VLR). In a VLR group signature, messages announcing the revocation of some users need only be processed by the verifiers; the signers are stateless. We present the Boneh-Shacham VLR group signature scheme, which has signatures even shorter than in BBS.1 Previous Publication The BLS short signature scheme of Section 3.3 and the notes on elliptic curve families in Section 2.3 originally appeared in “Short Signatures from the Weil Pairing,” joint work with Dan Boneh and Ben Lynn, of which an extended abstract was presented at Asiacrypt 2001 [27] and which appeared in the Journal of Cryptology [28|.
The BGLS aggregate signature scheme of Section 4.4 and the BGLS2 verifiably en- crypted signature scheme of Section 4.5 originally appeared in “Aggregate and Verifiably Encrypted Signatures from Bilinear Maps,” joint work with Dan Boneh, Craig Gentry, and Ben Lynn. which was presented at Eurocrypt 2003 [26]. The LMRS sequential aggregate signature scheme of Chapter 5 originally appeared in “Sequential Aggregate Signatures from Trapdoor Permutations,” joint work with Anna Lysyanskaya, Silvio Micali, and Leonid Reyzin, which was presented at Eurocrypt 2004 [79]. The BBS group signature scheme of Chapter 6, along with its extensions in Sections 7.3 originally appeared in “Short Group Signatures,” joint work with Xavier Boyen and Dan Boneh, which was presented at Crypto 2004 [24].
The BS group signature with verifier-local revocation of Section 7.
