Abstract
On Signatures of Knowledge
Anna Lysyanskaya
Brown University
In a traditional signature scheme, a signature \( \sigma \) on a message \( m \) is issued under a public key \( \mathrm{pk} \), and can be interpreted as follows: “The owner of the public key \( \mathrm{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.
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.
No video available