Balance between anonymity and accountability has been a central theme of my research. When accessing an online service provider, a user must present evidence that she is authorized to do so. For example, she may be authorized to participate in an on-line game once a day if she has a license to play. On the other hand, users are entitled to privacy, and should we require them to disclose their identities and show their credentials in the clear, their privacy is jeopardized: if a service provider's records are somehow leaked, or aggregated together with other service providers' records, a record of the user's activities will get exposed to the world, violating her privacy. It turns out that the two requirements --- the service provider's need to verify that the user is authorized and the user's need to protect her privacy --- do not contradict each other! What is needed here is an anonymous credential system that would allow a user to prove that she is authorized without revealing her identity, and, further, to obtain additional credentials without revealing additional information.

In a series of papers beginning with my Ph.D. thesis, I developed the first efficient and provably secure anonymous credential systems. Jointly with Jan Camenisch (IBM Zurich), I developed digital signature schemes that have efficient protocols that (1) allow a signer to issue a digital signature on a value (or a set of values) that is known to his client, but not to himself; (2) allow the client to prove to third parties that a value (or a set of values) known to him has been signed by the signer. Using such a signature, it is possible to both obtain credentials without revealing one's identity, and to prove possession of such credentials [CL01a,CL02b,CL04,BCKL08] (see below for the bibliography). As a result, a user need not reveal her identity or in fact any other information to any service providers, either the ones who issue credentials, or the ones that require credentials; in fact the data that the user submits cannot be linked to any other data that this user has submitted in other transactions.

In a series of subsequent papers, we demonstrated that an even better balance between anonymity and accountability can be achieved. Namely, we showed that it was possible to revoke anonymous credentials [CL02a]; to impose a limit on how many times a credential may be shown, and in what context, before the identity of the user is revealed [CHL05,CHL06,CHKLM06]; and many other aspects of this problem that may arise in practical scenarios [CLM07,BC+07].

Our work on anonymous credentials has attracted some industry attention: for example, it has been incorporated into the Trusted Computing Group's industry standard, and it has also been implemented by IBM. The reason that anonymous credentials are of interest in practice is that they give as much evidence of authorization as non-anonymous credentials, but the server provably does not learn anything about the identity of the client, and therefore provably cannot be liable for leaking private information in case of a break-in or compromise.

The question of balancing anonymity and accountability is not only interesting from the point of view of applications, but is also a stimulating topic for research in the theory of cryptography. For example, in the anonymous credentials setting, it is really the knowledge of one's credentials that enables one to participate in transactions. Recently, jointly with my Ph.D. student Melissa Chase, we showed that in fact knowledge of any secret information (for example, a satisfying assignment to a Boolean formula) that can be verified using some corresponding public information (i.e., the formula itself), can be used as a signing key for a digital signature. Where traditional signature schemes require signers to be associated with public keys generated in a certain way, signatures of knowledge associate signers directly with knowledge of a witness corresponding to any instance of any problem in NP [CL06]. This idea opens up an interesting and unifying research direction: how to turn knowledge of a secret into the power to sign.

This research is currently supported by the NSF Career grant CNS-0374661 and NSF grant CNS-0627553.

Annotated bibliography.

[BC+07] Mira Belenkiy, Melissa Chase, C. Chris Erway, John Jannotti, Alptekin Küpçü, John Jannotti, Anna Lysyanskaya, Eric Rachlin. "Making P2P Accountable without Losing Privacy." WPES 2007. workshop version.

Peer-to-peer systems have been proposed for a wide variety of applications, including file-sharing, web caching, distributed computation, cooperative backup, and onion routing. An important motivation for such systems is self-scaling. That is, increased participation increases the capacity of the system. Unfortunately, this property is at risk from selfish participants. The decentralized nature of peer-to-peer systems makes accounting difficult. We show that e-cash can be a practical solution to the desire for accountability in peer-to-peer systems while maintaining their ability to self-scale. No less important, e-cash is a natural fit for peer-to-peer systems that attempt to provide (or preserve) privacy for their participants. We show that e-cash can be used to provide accountability without compromising the existing privacy goals of a peer-to-peer system. We show how e-cash can be practically applied to a file sharing application. Our approach includes a set of novel cryptographic protocols that mitigate the computational and communication costs of anonymous e-cash transactions, and system design choices that further reduce overhead and distribute load. We conclude that provably secure, anonymous, and scalable peer-to-peer systems are within reach.

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 non-interactive 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 bilinear map. Namely, 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.

We create a credential system that lets a user anonymously authenticate at most N times in a single time period. A user withdraws a dispenser of N e-tokens. She shows an e-token to a verifier to authenticate herself; each e-token can be used only once, however, the dispenser automatically refreshes every time period. The only prior solution to this problem, due to amgård et al., uses protocols that are a factor of k slower for the user and verifier, where k is the security parameter. amgård et al. also only support one authentication per time period, while we support N. Because our construction is based on e-cash, we can use existing techniques to identify a cheating user, trace all of her e-tokens, and revoke her dispensers. We also offer a new anonymity service: glitch protection for basically honest users who (occasionally) reuse e-tokens. The verifier can always recognize a reused e-token; however, we preserve the anonymity of users who do not reuse e-tokens too often.

The main idea of electronic cash is that, even though the same party (a Bank) is responsible for giving out electronic coins, and for later accepting them for deposit, the withdrawal and the spending protocols are designed in such a way that it is impossible to identify when a particular coin was spent. I.e., the withdrawal protocol does not reveal any information to the Bank that would later enable it to trace how a coin was spent. Since a coin is represented by data, and it is easy to duplicate data, an electronic cash scheme requires a mechanism that prevents a user from spending the same coin twice (double-spending), for example by identifying double-spenders and tracing all transactions that they have carried out.

We give a scheme that allows a user to withdraw a wallet with $W$ coins, such that the space required to store these coins, and the complexity of the withdrawal protocol, are proportional to $\log W$, rather than to $W$. We achieve this without compromising the anonymity and unlinkability properties usually required of electronic cash schemes. We give a scheme that allows us to efficiently trace all coins that were spent by a double-spender.

The security of our construction relies on a mix of cryptographic assumptions about groups with bilinear maps, and is in the random oracle model.

We present the first electronic cash system that offers money-laundering prevention as an embedded technical feature. The best previously known e-cash systems realize this protection externally through a trusted third party, if at all. In our system, each merchant has an individual, publicly-known bound on the amount of business he may conduct with any single customer. For example, a politician may be able to accept up to $1,000 from any one donor, while a charity may be able to accept up to $1,000,000. A user may withdraw, and anonymously and unlinkably spend an unlimited number of coins, so long as she does not: (1) spend more coins that she withdrew, or (2) exceed the spending limit with any merchant.

If a user violates either of these conditions, we provide three increasingly stringent alternatives. The system can be designed so that, once a user violates a system condition: (1) the violation is detected, (2) the violation is detected and the user's identity is revealed, and (3) in addition to (2), all of the user's previous spendings can be quickly identified. In the best previously known schemes, money laundering is often hard to detect, and even if detected requires a trusted third party to take any additional action.

Our scheme is based on the recent e-cash system of Camenisch, Hohenberger, and Lysyanskaya. It is provably secure under the same computational assumptions as the CHL system.

A credential system is a system in which users can obtain credentials from organizations and demonstrate possession of these credentials. Such a system is anonymous when transactions carried out by the same user cannot be linked. An anonymous credential system is of significant practical relevance because it is the best means of providing privacy for users. In this paper we propose a practical anonymous credential system that is based on the strong RSA assumption and the decisional Diffie-Hellman assumption modulo a safe prime product and is considerably superior to existing ones: (1) We give the first practical solution that allows a user to unlinkably demonstrate possession of a credential as many times as necessary without involving the issuing organization. (2) To prevent misuse of anonymity, our scheme is the first to offer optional anonymity revocation for particular transactions. (3) Our scheme offers separability: all organizations can choose their cryptographic keys independently of each other. Moreover, we suggest more effective means of preventing users from sharing their credentials, by introducing all-or-nothing sharing: a user who allows a friend to use one of her credentials once, gives him the ability to use all of her credentials, i.e., taking over her identity. This is implemented by a new primitive, called circular encryption, which is of independent interest, and can be realized from any semantically secure cryptosystem in the random oracle model.

An accumulator scheme, as introduced by Benaloh and de Mare and further studied by Baric and Pfitzmann, is an algorithm that allows one to hash a large set of inputs into one short value, called the accumulator, such that there is a (short) witness that a given input was incorporated into the accumulator. At the same time, it is infeasible to find a witness for a value that was not accumulated.

We put forward the notion of a dynamic accumulator, which is an accumulator that allows one to dynamically add and delete inputs, such that the cost of an add or delete is independent of the number of accumulated values. We achieve this under the strong RSA assumption. For this construction, we also show an efficient zero-knowledge protocol for proving that a committed value is in the accumulator.

Dynamic accumulators enable efficient membership revocation in the anonymous setting. Our construction is especially suitable for membership revocation in group signature and identity escrow schemes, such as the one due to Ateniese et al., and efficient revocation of credentials in anonymous credential systems, such as the one due to Camenisch and Lysyanskaya. Applying our method to these schemes enables membership revocation and yet does not significantly increase the complexity of any of the operations. In particular, the cost of a membership verification or credential showing increases by only a small constant factor, less than 2. All previously known methods (such as the ones due to Bresson and Stern and Ateniese and Tsudik) incur an increase in these costs that is linear in the number of members.

Digital signature schemes are a fundamental cryptographic primitive, of use both in its own right, and as a building block in cryptographic protocol design. In this paper, we propose a practical and provably secure signature scheme and show protocols (1) for issuing a signature on a committed value (so the signer has no information about the signed value), and (2) for proving knowledge of a signature on a committed value. This signature scheme and corresponding protocols are a building block for the design of anonymity-enhancing cryptographic systems, such as electronic cash, group signatures, and anonymous credential systems. The security of our signature scheme and protocols relies on the Strong RSA assumption. These results are a generalization of the anonymous credential system of Camenisch and Lysyanskaya.

We propose a new and efficient signature scheme that is provably secure in the plain model. The security of our scheme is based on a discrete-logarithm-based assumption put forth by Lysyanskaya, Rivest, Sahai, and Wolf (LRSW) who also showed that it holds for generic groups and is independent of the decisional Diffie-Hellman assumption. We prove security of our scheme under the LRSW assumption for groups with bilinear maps. We then show how our scheme can be used to construct efficient anonymous credential systems as well as group signature and identity escrow schemes. To this end, we provide efficient protocols that allow one to prove in zero-knowledge the knowledge of a signature on a committed (or encrypted) message and to obtain a signature on a committed message.

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 this paper we consider schemes that allow 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 is in L has signed message m.'' We refer to such schemes as signatures of knowledge. 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 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 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.

An electronic cash (e-cash) scheme lets a user withdraw money from a bank and then spend it anonymously. E-cash can be used only if it can be securely and fairly exchanged for electronic goods or services. In this paper, we introduce and realize endorsed e-cash. An endorsed e-coin consists of a lightweight endorsement $x$ and the rest of the coin which is meaningless without $x$. We reduce the problem of exchanging e-cash to that of exchanging endorsements. We demonstrate the usefulness of endorsed e-cash by exhibiting simple and efficient solutions to two important problems: (1) optimistic and unlinkable fair exchange of e-cash for digital goods and services; and (2) onion routing with incentives and accountability for the routers. Finally, we show how to represent a set of $n$ endorsements using just one endorsement; this means that the complexity of the fair exchange protocol for $n$ coins is the same as for one coin, making e-cash all the more scalable and suitable for applications. Our fair exchange of multiple e-coins protocol can be applied to fair exchanges of (almost) any secrets.

Pseudonym systems allow users to interact with multiple organizations anonymously, using pseudonyms. The pseudonyms cannot be linked, but are formed in such a way that a user can prove to one organization a statement about his relationship with another. Such a statement is called a credential. Previous work in this area did not protect the system against dishonest users who collectively use their pseudonyms and credentials, i.e., share an identity. Previous practical schemes also relied very heavily on the involvement of a trusted center. In the present paper we give a formal definition of pseudonym systems where users are motivated not to share their identity, and in which the trusted center's involvement is minimal. We give theoretical constructions for such systems based on any one-way function. We also suggest an efficient and easy-to-implement practical scheme.