Skip to main content

Über dieses Buch

As a beginning graduate student, I recall being frustrated by a general lack of acces sible sources from which I could learn about (theoretical) cryptography. I remember wondering: why aren’t there more books presenting the basics of cryptography at an introductory level? Jumping ahead almost a decade later, as a faculty member my graduate students now ask me: what is the best resource for learning about (various topics in) cryptography? This monograph is intended to serve as an answer to these 1 questions — at least with regard to digital signature schemes. Given the above motivation, this book has been written with a beginninggraduate student in mind: a student who is potentially interested in doing research in the ?eld of cryptography, and who has taken an introductory course on the subject, but is not sure where to turn next. Though intended primarily for that audience, I hope that advanced graduate students and researchers will ?nd the book useful as well. In addition to covering various constructions of digital signature schemes in a uni?ed framework, this text also serves as a compendium of various “folklore” results that are, perhaps, not as well known as they should be. This book could also serve as a textbook for a graduate seminar on advanced cryptography; in such a class, I expect the entire book could be covered at a leisurely pace in one semester with perhaps some time left over for excursions into related topics.



Setting the Stage


Chapter 1. Digital Signatures: Background and Definitions

Loosely speaking, a

digital signature scheme

offers a cryptographic analogue of handwritten signatures that, in fact, provides much stronger security guarantees. Digital signatures serve as a powerful tool and are now accepted as legally binding in many countries; they can be used for certifying contracts or notarizing documents, for authentication of individuals or corporations, and as components of more complex protocols. Digital signatures also enable the secure distribution and transmission of public keys and thus, in a very real sense, serve as the foundation for all of public-key cryptography.

Jonathan Katz

Chapter 2. Cryptographic Hardness Assumptions

As noted in the previous chapter, it is impossible to construct a digital signaturescheme that is secure against an all-powerful adversary. Instead, the best we canhope for is to construct schemes that are secure against

computationally bounded

adversaries (that, for our purposes, means adversaries running in probabilistic polynomialtime). Even for this “limited” class of adversaries, however, we do not currentlyhave any constructions that can proven, unconditionally, to be secure. In fact,it is not too difficult to see that the existence of a secure signature scheme would imply




, a breakthrough in complexity theory. (While there is general belief that



is true, we seem very far away from being able to prove this.) Actually,as we will see below, the existence of a secure signature scheme implies the existenceof one-way functions, something not known to follow from



and thusan even stronger result. (Informally, the issue is that



only guarantees the existence of problems that are hard

in the worst case

. But a secure signature scheme isrequired to be “hard to break”

on the average

— in particular, for “average” publickeys generated by signers.)

Jonathan Katz

Digital Signature Schemes without Random Oracles


Chapter 3. Constructions Based on General Assumptions

Our objective in this chapter is to present a construction of a digital signature scheme based on the minimal assumption (cf. Theorem 2.1) that one-way functions exist. Along the way we will see a relatively simple construction, due to Lamport, of a


signature scheme based on the same assumption. We warn the reader at the outset that efficiency will not be a consideration here; we aim instead for generality (first) and simplicity of exposition (second). Interestingly, although several improved constructions of one-time signatures from one-way functions or permutations are known, the construction of a CMA-secure signature described in this chapter is essentially the best known (from any of the general assumptions discussed in the previous chapter); improving the efficiency of this generic construction remains an interesting and important open question.

Jonathan Katz

Chapter 4. Signature Schemes Based on the (Strong) RSA Assumption

The signature schemes described in the previous chapter have the advantage of being based on very weak cryptographic assumptions, but have the drawback of being incredibly inefficient. (Even the Lamport scheme, which could conceivably be used, has very large public keys and signatures.) It is natural to wonder whether relying on stronger, more specific assumptions might yield more efficient schemes. Unfortunately, progress in this direction has been limited: only a handful of schemes are known that are more efficient than the “generic” constructions of the previous chapter and, of these, even fewer are efficient enough to compete with the signature schemes currently used in practice.1 In fact, and somewhat disappointingly, the


schemes we currently have that come close to the efficiency of signature schemes currently in use are based on relatively “new” cryptographic assumptions discussed in this and the following chapter. (Admittedly, this point is debatable and depends to some extent on what one takes as his measure of efficiency.)

Jonathan Katz

Chapter 5. Constructions Based on Bilinear Maps

In the past 10 years cryptographic constructions based on

bilinear maps

have become extremely popular, most prominently following their use in constructing identity-based encryption schemes. Bilinear maps have also led to several efficient signature schemes, and we explore two such constructions here.

Jonathan Katz

Digital Signature Schemes in the Random Oracle Model


Chapter 6. The Random Oracle Model

The signature schemes described in the previous chapters, whether based on the RSA/strong RSA assumptions or bilinear maps, represent essentially the extent of what is currently known regarding



provably secure

signature schemes.

Jonathan Katz

Chapter 7. Full-Domain Hash (and Related) Signature Schemes

An important class of signature schemes proven secure in the random oracle model is given by the

full-domain hash

(FDH) signature scheme and its variants. In addition to being simple and natural, as well as quite efficient, constructions in this family are also the basis for standardizes signature schemes that are widely used.

Jonathan Katz

Chapter 8. Signature Schemes from Identification Schemes

There are currently two main techniques for constructing signature schemes in the random oracle model. The first technique uses the “full-domain hash” approach, and several schemes designed using this approach were introduced in the previous chapter. Here we cover the second central method, in which signature schemes are derived from so-called

identification schemes

. We note up front that there is a rich literature studying identification schemes in their own right; however, we limit ourselves to a discussion of only those aspects that are most directly relevant to the construction of signature schemes.

Jonathan Katz


Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.



Product Lifecycle Management im Konzernumfeld – Herausforderungen, Lösungsansätze und Handlungsempfehlungen

Für produzierende Unternehmen hat sich Product Lifecycle Management in den letzten Jahrzehnten in wachsendem Maße zu einem strategisch wichtigen Ansatz entwickelt. Forciert durch steigende Effektivitäts- und Effizienzanforderungen stellen viele Unternehmen ihre Product Lifecycle Management-Prozesse und -Informationssysteme auf den Prüfstand. Der vorliegende Beitrag beschreibt entlang eines etablierten Analyseframeworks Herausforderungen und Lösungsansätze im Product Lifecycle Management im Konzernumfeld.
Jetzt gratis downloaden!