Digital Signatures

Jonathan Katz is an associate professor in the Department of Computer Science at the University of Maryland. Active in the cryptography research community, he has held visiting positions at UCLA, '{E}cole Normale Sup'{e}rieure, and IBM. He has given several introductory lectures on cryptography to general audiences in both industry and government, and is an author of the textbook "Introduction to Modern Cryptography".

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.

Structured for the needs of professionals, as well as graduate level computer science students, this is the first reference to address the methodology, cryptographic and computational demands of a secure web. Using the author's observations of duality in two well-known cryptographic 'primitives', Digital Signatures introduces new strategies and methodologies for designing provably secure group-signatures based on traitor tracing schemes.

Setting the Stage.- Digital Signatures: Background and Definitions.- Cryptographic Hardness Assumptions.- Digital Signature Schemes without Random Oracles.- Constructions Based on General Assumptions.- Signature Schemes Based on the (Strong) RSA Assumption.- Constructions Based on Bilinear Maps.- Digital Signature Schemes in the Random Oracle Model.- The Random Oracle Model.- Full-Domain Hash (and Related) Signature Schemes.- Signature Schemes from Identification Schemes.