P-signatures and Noninteractive Anonymous Credentials
In this paper, we introduce P-signatures. A P-signature scheme consists of a signature scheme, a commitment scheme, and (1) an interactive protocol for obtaining a signature on a committed value; (2) a non − interactive proof system for proving that the c
- PDF / 528,463 Bytes
- 19 Pages / 430 x 660 pts Page_size
- 30 Downloads / 172 Views
Brown University {mira, melissa, anna}@cs.brown.edu 2 KU Leuven [email protected]
Abstract. In this paper, we introduce P-signatures. A P-signature scheme consists of a signature scheme, a commitment scheme, and (1) an interactive protocol for obtaining a signature on a committed value; (2) a non-interactive proof system for proving that the contents of a commitment has been signed; (3) a noninteractive proof system for proving that a pair of commitments are commitments to the same value. We give a definition of security for P-signatures and show how they can be realized under appropriate assumptions about groups with a bilinear map. We make extensive use of the powerful suite of non-interactive proof techniques due to Groth and Sahai. Our P-signatures enable, for the first time, the design of a practical non-interactive anonymous credential system whose security does not rely on the random oracle model. In addition, they may serve as a useful building block for other privacy-preserving authentication mechanisms.
1 Introduction Anonymous credentials [Cha85, Dam90, Bra99, LRSW99, CL01, CL02, CL04] let Alice prove to Bob that Carol has given her a certificate. Anonymity means that Bob and Carol cannot link Alice’s request for a certificate to Alice’s proof that she possesses a certificate. In addition, if Alice proves possession of a certificate multiple times, these proofs cannot be linked to each other. Anonymous credentials are an example of a privacy-preserving authentication mechanism, which is an important theme in modern cryptographic research. Other examples are electronic cash [CFN90, CP93, Bra93, CHL05] and group signatures [CvH91, CS97, ACJT00, BBS04, BW06, BW07]. In a series of papers, Camenisch and Lysyanskaya [CL01, CL02, CL04] identified a key building block commonly called “a CL-signature” that is frequently used in these constructions. A CL-signature is a signature scheme with a pair of useful protocols. The first protocol, called Issue, lets a user obtain a signature on a committed message without revealing the message. The user wishes to obtain a signature on a value x from a signer with public key pk . The user forms a commitment comm to value x and gives comm to the signer. After running the protocol, the user obtains a signature on x, and the signer learns no information about x other than the fact that he has signed the value that the user has committed to. The second protocol, called Prove, is a zero-knowledge proof of knowledge of a signature on a committed value. The prover has a message-signature pair (x, σpk (x)). R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 356–374, 2008. c International Association for Cryptologic Research 2008
P-signatures and Noninteractive Anonymous Credentials
357
The prover has obtained it by either running the Issue protocol, or by querying the signer on x. The prover also has a commitment comm to x. The verifier only knows comm. The prover proves in zero-knowledge that he knows a pair (x, σ) and a value open such that VerifySig(pk , x, σ) = accept an
Data Loading...
