We formally define the notion of a signature of knowledge. We begin by extending the traditional definition of digital signature schemes, captured by Canetti's ideal signing functionality, to the case of signatures of knowledge. We then give an alternative definition in terms of games that also seems to capture the necessary properties one may expect from a signature of knowledge. We then gain additional confidence in our two definitions by proving them equivalent.
We construct signatures of knowledge under standard complexity assumptions in the common-random-string model.
We then extend our definition to allow signatures of knowledge to be \emph{nested} i.e., a signature of knowledge (or another accepting input to a UC-realizable ideal functionality) can itself serve as a witness for another signature of knowledge. Thus, as a corollary, we obtain the first \emph{delegatable} anonymous credential system, i.e., a system in which one can use one's anonymous credentials as a secret key for issuing anonymous credentials to others.
Category / Keywords: signature schemes, NIZK, proof of knowledge, UC, anonymous Publication Info: this is the full version of a paper which will appear in CRYPTO 06 Date: received 1 Jun 2006, last revised 8 Aug 2006 Contact author: mchase at cs brown edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20060808:225010 (All versions of this report) Short URL: ia.cr/2006/184 Discussion forum: Show discussion | Start new discussion