When living in a society and interacting with others, we often have to prove to them who we are. We do this in order for the others to decide, whether to perform certain transactions with us, e.g., sell us something or allow us to use something. To prove who we are, we typically use our identity cards or other documents that state who we are and what we are entitled to.
Often, it is not necessary to learn someone’s identity for deciding, whether he or she is entitled to some service. For example, to sell wine, the merchant only has to determine whether the buyer is at least 18 years old, but not his/her name, or even the exact age. To permit someone to use public transportation, the conductor or driver has to verify that the person has purchased or otherwise obtained the privilege to ride in this vehicle. To permit someone to vote in an election, his/her eligibility has to be determined; this determination may take widely different forms depending on the election (whether it is for a government, a board of a company or school, or something else). A very general example of the use of anonymous credentials is the use of cash when buying and selling things.
In the digital world, a credential takes the form of a certificate, issued by an authority that has determined the relevant attributes of the person, and/or received the relevant consideration from that person to whom the certificate has been given. The credential may be meant for multiple use, which is the case for identity cards. It may also be meant for single use, or limited-time use, for example, the public transportation tickets, or gift cards. When we present that credential to a merchant, he confirms two things:
(1) the credential has been issued by an authority that the merchant recognises, i.e. the credential has been signed with the public key of a recognised authority;
(2) the attributes listed in the credential satisfy necessary conditions to get the service from the merchant.
Assuming that the conditions the merchant checks are known to us, what if we could hide the parts of the credential that are not necessary for evaluating these conditions? E.g., when performing a purchase that requires the age of at least 18 years, the customer could show the merchant his identity card, but cover both the name listed there, as well as the birthday, except for the thousands position of the year of birth, which reads “1”. Even this would give the merchant more information than necessary, as it proves that the customer is at least almost 20 years old. More importantly, even when covering these parts of the document, the merchant can still figure out that it is a government-issued identity card, and hence the birthday information may be trusted.
How can we achieve similar functionality using cryptographic tools? A digital signature is intended to prevent any modification of an underlying document. We are going to use zero-knowledge proofs: instead of handing one’s certificate with the accompanying signature over to the merchant, the customer only presents a proof that he or she is in a possession of a credential that satisfies the properties (1) and (2) above. Zero-knowledge proofs are a more computationally intensive cryptographic primitive, but the proofs for the statements (1) and (2) may still be rather efficient (note that the complexity of (2) varies depending on the exact condition being verified, but these conditions are typically not complex). Indeed, the functionality necessary for the customer was demonstrated on a smart-card already more than ten years ago.
Using zero-knowledge proofs for the statements of type (1) and (2), we achieve privacy for a single transaction. What other privacy properties are needed? An important property is unlinkability - different transactions of the same customer should not be recognised as being done by the same person. We want this property to hold even if the merchant participating in the transaction is the same, and even if the authority issuing the credentials cooperates with the merchant. Indeed, the lack of unlinkability would allow cooperating merchants and authorities to build user profiles, which, even without actual names, could reveal a lot about them.
When services are provided digitally, the merchant still needs an identity of the customer in order to target the service towards him/her. Here, the targeting could mean the encryption of the digital content in a manner that only this customer can decrypt. For this purpose, the customer creates several pseudonyms for himself. The unlinkability of different transactions will hold, if different pseudonyms have been used in them. In general, the customer will approach the credential-issuing authority many times, requesting credentials for different pseudonyms. Each time the authority verifies the attributes of that customer, and creates a certificate for the pseudonym that the customer chose.
The unlinkability property now requires that the credential-issuing authority may not see the pseudonym that will be included in the credential. If he could see it, he could build up a mapping between the real identities of the customers (which the authority needs to know in order to verify their attributes), and the pseudonyms. He will then be able to assist the merchants to link transactions done with different pseudonyms. To be able to issue credentials like that, we need another cryptographic primitive – blind signatures. This primitive allows the first party to request a signature to a message he has chosen from the second party, without the second party seeing it. In the physical world, this would correspond to the second party signing at the bottom of a sheet of a paper and then tamper-evidently folding it, while the message on this sheet is not shown to him/her. For anonymous credentials, the blind signatures have to be carefully used during issuing, so that only the pseudonym is blinded, but the attributes are controlled by the authority.
In the physical world, we know that one should not sign a piece of paper if one does not know what is written on it. In the digital world, there is additional flexibility that justifies blind signatures. Namely, the signing key also comes with a certificate which specifies the possible uses of this key. Hence, the credential-issuing authority cannot, e.g., accidentally sign away the deed to its house.
The anonymity of the credentials does not have to be absolute, it may be revocable in certain situations. An important example is the creation of single-use credentials, e.g., public transportation tokens, or, more generally, digital cash. As the tokens are digital, they can be copied similarly to any other digital information. However, it is possible to embed the identity of the customer in the credential in such a manner, that nothing of this identity is revealed when the credential is presented to a merchant a single time (the presentation is in the form of a cryptographic protocol, involving the customer responding to a challenge message from the merchant), but everything is revealed when it is presented twice (hence the customer has to respond to two different challenges). The revelation can happen either at the merchant, or, if the same credential was presented to different merchants, then later at the credential-issuing authority to which all merchants send the spent credentials. Such revelation mechanism may serve as a powerful disincentive for double-spending.
Written by Peeter Laud