Non-interactive zero-knowledge (NIZK) proof systems allow one to prove that a given statement is true without revealing any additional information. Several results consider the malleabiilty of proof systems - the extent to which a valid proof can be modified to produce another valid proof for a related statement. However these works consider malleability a weakness, and focus on techniques for reducing malleability of proof systems. Here, we will show that malleability can have positive applications as well. In particular, we define a property called randomizability, and show that this can be useful in privacy applications, and in particular in the area of anonymous credentials.
Anonymous credential systems allow users to anonymously obtain credentials from organizations, and to anonymously and unlinkably prove possesion of valid credentials. Often in practice, however, a user authenticates using some credential chain: a root organization gives a credential to an intermediate party who can in turn use this to issue credentials to user. We address this problem by presenting the first efficient delegatable anonymous credential scheme. In such a scheme, a party can receive credentials from an organization, and then anonymously and unlinkably issue delegated credentials to other users, who can in turn delegate these credentials to another level. Then a user can prove possession of a valid chain of credentials of a given length without revealing any other identifying information. This talk will describe our result and outline some of the main techniques used to achieve it.