In a traditional signature scheme, a signature $\sigma$ on a message
$m$ is issued under a public key $\pk$, and can be interpreted as
follows: "The owner of the public key $\pk$ and its corresponding
secret key has signed message $m$." In contrast, here we consider a
scheme that allows one to issue signatures on behalf of any NP
statement, that can be interpreted as follows: "A person in possession
of a witness $w$ to the statement that $x \in L$ has signed message
$m$." We refer to such schemes as _signatures of knowledge_.
Our first contribution is definitional. We formally define the notion
of a signature of knowledge. We first give a definition in terms of a
game between an adversary and a challenger. We then give evidence that
this definition captures all and only the necessary properties one may
expect from a signature of knowledge by defining an ideal functionality
for signatures of knowledge and showing that a signature of knowledge
UC-realizes the ideal functionality if and only if it satisfies our
definition.
Further, we construct signatures of knowledge under standard complexity
assumptions in the common-random-string model.
It is important to note that our definition allows signatures of
knowledge to be _nested_ i.e., a signature of knowledge can itself
serve as a witness for another signature of knowledge. Thus, as a
corollary, we obtain the first _delegatable_ anonymous credential
system, i.e., a system in which one can use one's anonymous credential
as a secret key for issuing more anonymous credentials.
This is joint work with Melissa Chase.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.