Concepts and features

Concepts and Features of Privacy-Preserving Attribute-Based Credentials#

The figure below gives an overview of the entities involved in Privacy-ABC systems and the interactions between them. These entities are users, issuers, verifiers, inspectors and revocation authorities.

• The user is at the center of the picture, collecting credentials from various issuers and controlling which information from which credentials she presents to which verifiers.

• An issuer issues credentials to users, thereby vouching for the correctness of the information contained in the credential with respect to the User to whom the credential is issued. Each issuer generates a secret issuance key and publishes the issuer parameters that include the corresponding public verification key.

• A verifier protects access to a resource or service that it offers by imposing restrictions on the credentials that users must own and the information from these credentials that users must present in order to access the service.

• A revocation authority (optional) is responsible for revoking issued credentials, so that these credentials can no longer be used to generate a presentation token. Each revocation authority generates and publishes its revocation parameters.

• An inspector (optional) is a trusted authority who can de-anonymize presentation tokens under specific circumstances. At setup, each inspector generates a private decryption key and a corresponding public encryption key.

In a nutshell, an attribute-based credential contains attributes-value pairs that are certified by a trusted issuer w.r.t. the user. A credential can also specify one or more revocation authorities who are able to revoke the credential if necessary for some reason. Using her credentials, a user can form a presentation token that contains a subset of the certified attributes, provided that the corresponding credentials have not been revoked. Additionally, some of the attributes can be encoded in the presentation token so that they can only be retrieved by an inspector. Receiving a presentation token from a user, a verifier checks whether the presentation token is valid w.r.t. the relevant issuers' public keys and inspector public keys and the latest revocation information. If the verification succeeds, the verifier will be convinced that the attributes contained in the presentation token are vouched for by the corresponding issuers.

Informally, a secure realization of a Privacy-ABC system must guarantee that

• users can only generate a valid presentation token if they were indeed issued the corresponding credentials that have not been revoked,

• that attributes encoded in the presentation token for an inspector can indeed be retrieved by that inspector, and

• that the presentation tokens do not reveal any further information about the users other than the attributes contained in them.

We now provide a brief explanation of the main features supported by Privacy-ABCs, with a focus on the ones that were not modeled so far in existing identity frameworks.

Pseudonyms

Each user can generate a secret key. Unlike traditional public-key authentication schemes, however, there is no single public key corresponding to the secret key. Rather, the user can generate as many public keys as she wishes. These public keys are called pseudonyms in Privacy-ABCs. Pseudonyms are cryptographically unlinkable, meaning that given two different pseudonyms, one cannot tell whether they were generated from the same or from different secret keys. By generating a different pseudonym for every verifier, users can thus be known under different unlinkable pseudonyms to different sites, yet use the same secret key to authenticate to all of them.

While it is sufficient for users to generate a single secret key, they can also have multiple secret keys. A secret key can be generated by a piece of trusted hardware (e.g., a smart card) that stores and uses the key in computations (e.g., to generate pseudonyms), but that never reveals the key. The key is thereby bound to the hardware, in the sense that it can only be used in combination with the hardware.

There are situations, however, where the possibility to generate an unlimited number of unlinkable pseudonyms is undesirable. For example, in an online opinion poll, users should not be able to bias the result by entering multiple votes under different pseudonyms. In such situations, the verifier can request a special pseudonym called a scope-exclusive pseudonym, which is unique for the user’s secret key and a given scope string. Scope-exclusive pseudonyms for different scope strings remain unlinkable. By using the URL of the opinion poll as the scope string, for example, the verifier can ensure that each user can only register a single pseudonym to vote.

Credentials and Key Binding

A credential is a certified container of attributes issued by an issuer to a user. Formally, an attribute is described by the attribute type that determines the semantics of the attribute (e.g., first name) and the attribute value that determines its contents (e.g., “John”). By issuing a credential, the issuer vouches for the correctness of the contained attributes with respect to the user.

Optionally, a credential can be bound to a user’s secret key, i.e., it cannot be used without knowing the secret key. We call this option key binding. It is somewhat analogous to traditional public-key certificates, where the certificate contains the CA’s signature on the user’s public key, but unlike traditional public-key certificates, a Privacy-ABC is not bound to a unique public key: it is only bound to a unique secret key. A user can derive as many pseudonyms as she wishes from this secret key and (optionally) show that they were derived from the same secret key that underlies the credential. As an extra protection layer, the credentials can also be bound to a trusted physical device, such as a smart card, by keeping the secret key in a protected area of the device.

Presentation

To authenticate to a verifier, the user first obtains the presentation policy that describes which credentials the user must present and which information from these credentials she must reveal. If the user possesses the necessary credentials, she can derive from these credentials a presentation token that satisfies the presentation policy. The presentation token can be verified using the issuer parameters of all credentials underlying the presentation token.

Presentation tokens derived from Privacy-ABCs only reveal the attributes that were explicitly requested by the presentation policy – all the other attributes contained in the credentials remain hidden. Moreover, presentation tokens are cryptographically unlinkable (meaning no collusion of issuers and verifiers can tell whether two presentation tokens were generated by the same user or by different users) and untraceable (meaning that no such collusion can correlate a presentation token to the issuance of the underlying credentials). Of course, presentation tokens are only as unlinkable as the information they intentionally reveal.

Rather than requesting and revealing full attribute values, presentation policies and tokens can also request and reveal predicates over one or more issued attributes. For example, a token could reveal that the name on the user’s credit card matches that on her driver’s license, without revealing the name. As another example, a token could reveal that the user’s birthdate is before January 1st, 1994, without revealing her exact birthdate.

When the presentation policy requires the posession of a key-bound credential, the derived presentation token from such a credential always contains an implicit proof of knowledge of the underlying secret key. Thus, the verifier can be sure that the rightful owner of the credential was involved in the creation of the presentation token. In case the secret key of the user is rather a device key, i.e., a key that is kept on a trusted device and can not be extracted from the device, then the proof of knowledge of the key is performed on the device and included in presentation token generation. Thus, for credentials that are key-bound to a physical device it is impossible to create a presentation token without the device.

Issuance

In the simplest setting, an issuer knows all attribute values to be issued and simply embeds them into a credential. Privacy-ABCs also support advanced issuance features where attributes are blindly “carried over” from existing credentials, without the issuer becoming privy to their values. Similarly, the issuer can blindly issue self-claimed attribute values (i.e., not certified by an existing credential), carry over the secret key to which a credential is bound, or assign a uniformly random value to an attribute such that the issuer cannot see it and the user cannot bias it.

Advanced issuance is an interactive protocol between the user and the issuer. In the first move, the issuer provides the user with an issuance policy that consists of a presentation policy specifying which pseudonyms and/or existing credentials the user must present, and of a credential template specifying which attributes or secret keys of the newly issued credential will be generated at random or carried over from credentials or pseudonyms in the presentation policy. In response, the user sends an issuance token containing a presentation token that satisfies the issuance policy. Then the (possibly multi-round) cryptographic issuance protocol ensues, at the end of which the user obtains the new credential.

Inspection

Absolute user anonymity in online services easily leads to abuses such as spam, harassment, or fraud. Privacy-ABCs provide the option to add accountability for misbehaving users through a feature called inspection. Here, a presentation token contains one or more credential attributes that are encrypted under the public key of a trusted inspector. The verifier can check that the correct attribute values were encrypted, but cannot see their actual values. The inspection grounds describe the circumstances under which the verifier may call upon the inspector to recover the actual attribute values. The inspector is trusted to collaborate only when the inspection grounds have been met; verifiers cannot change the inspection grounds after receiving a presentation token, as the grounds are cryptographically tied to the token.

The presentation policy specifies which attributes from which credentials have to be encrypted, together with the inspector public keys and inspection grounds under which they have to be encrypted.

Revocation

Credentials may need to be revoked for several reasons: the credential and the related user secrets may have been compromised, the user may have lost her right to carry a credential, or some of her attribute values may have changed. In such cases, credentials need to be revoked globally and we call this issuer-driven revocation. Sometimes credentials may be revoked only for specific contexts. For example, a hooligan may see his digital identity card revoked for accessing sport stadiums, but may still use it for all other purposes. We call this verifier-driven revocation.

Revocation for Privacy-ABCs is cryptographically more complicated than for classical certificates, but many mechanisms with varying efficiency exist [add refs]. Bar a few exceptions, all of them can be used for both issuer-driven and verifier-driven revocation.

We describe revocation in a generic mechanism-agnostic way and consider credentials to be revoked by dedicated revocation authorities. They are separate entities in general, but may be under the control of the issuer or verifier in particular settings. The revocation authority publishes static revocation authority parameters and periodically publishes the most recent revocation information. When creating presentation tokens, users prove that their credentials have not been revoked, possibly using non-revocation evidence that they fetch and update from the revocation authority. The revocation authority to be used is specified in the issuer parameters for issuer-driven revocation and in the presentation policy for verifier-driven revocation. When a credential is subject to issuer-driven revocation, a presentation token related to this credential must always contain a proof that the presented credential has not been revoked. Issuer-driven revocation is performed based on the revocation handle, which is a dedicated unique attribute embedded in a credential. Verifier-driven revocation can be performed based on any combination of attribute values, possibly even from different credentials. This allows the revocation authority for example to exclude certain combinations of first names and last names to be used in a presentation token.