Guest blog by Greg Bernstein, Dave Longley, Manu Sporny, and Kim Hamilton Duffy

Following the IETF/IRTF Crypto Forum Research Group’s adoption of the BBS Blind Signatures and BBS per Verifier Linkability (“BBS Pseudonym”) specifications, this blog describes historical context and details of cryptographic pseudonyms, as well as the privacy features they enable.

The discussion of cryptographic pseudonyms for privacy preservation has a long history, with Chaum’s 1985 popular article “Security without identification: transaction systems to make big brother obsolete” (Chaum1985) addressing many of the features of such systems such as unlinkability and constraints on their use such as one pseudonym per organization and accountability for pseudonym use. Although Chaum’s proposal makes use of different cryptographic primitives than we will use here, one can see similarities in the use of both secret and “public” information being combined to create a cryptographic pseudonym.

Lysyanskaya’s 2000 paper (Lysya2000) also addresses the unlinkable aspects of pseudonyms but also provides protections against dishonest users. In addition they provide practical constructions similar to those used in our draft based on discrete logarithm and sigma protocol based ZKPs. Finally as part of the ABC4Trust project three flavors of pseudonyms were defined:

1. Verifiable pseudonyms are pseudonyms derived from an underlying secret key.
2. Certified pseudonyms are certified pseudonyms derived from a secret key that also underlies an issued credential.
3. Scope-exclusive pseudonyms are verifiable pseudonyms that are guaranteed to be unique per scope string and per secret key.

The BBS based pseudonyms in our draft are aimed primarily at providing the functionality of the pseudonym flavors 2 and 3 above.

How BBS is Fundamentally Better for Solving Dishonest Holder Fraud

Beyond the usual anti-forgery and tamper-evident protections that digital signatures provide, there are two different types of credential fraud that unlinkable credentials need to mitigate: third-party fraud and first-party fraud.

Third-party fraud is when one party uses another party's credentials without their knowledge or approval. This involves the theft of an honest holder's credentials.

First-party fraud is when a legitimate credential holder intentionally allows other parties to covertly use their credentials. This involves not the theft of credentials, but rather, a dishonest holder.

BBS signatures provides two different security features, one to address each of these cases:

1. Holder Multifactor Authentication

This security feature binds a BBS credential to a particular secret that only the holder knows and that an honest holder will not share access to nor use of. When a holder presents a BBS credential, a verifier can require that the holder prove use of this secret, thereby enforcing this protection on the holder's behalf. This is an anti-theft mechanism for mitigating third-party fraud.

Note: This feature is sometimes called "holder binding", but it might be more accurately understood as "Holder Multifactor Authentication". This is because the holder is not themselves bound to the credential and it is not a mitigation for first-party fraud. It instead works like another MFA device does when performing authentication. If a dishonest holder shares that MFA device or an API to use it, then someone else can unlinkably present their credential (with the holder's approval -- perhaps even for a fee). Stopping dishonest holders from doing this is a significant challenge that involves locking down users' hardware and software – and a single failure in this scheme could potentially result in an unlimited number of unlinkable, fraudulent presentations. This feature is therefore not a protection for verifiers, but rather one for honest holders against theft. With this in mind, it can be implemented such that a holder is free to use software or hardware of their choice to provide the protection, without requiring specific approval from the issuer.

2. Pseudonyms

This security feature binds a BBS credential to a secret that is constructed from inputs from both the holder and the issuer. When a holder presents a BBS credential, a verifier can require that the holder present a pseudonym that is based on this secret and a contextual identifier. Each time the same BBS credential is presented using the same contextual identifier, the pseudonym will be the same. This prevents a dishonest holder from covertly enabling an unlimited number of unlinkable presentations of their credential by any parties they authorize. It is an anti-cloning mechanism for mitigating first-party fraud.

Contextual identifiers can be any value, but need to be agreed upon between the verifier and the holder for a given use case. To give some examples for the presentation of credentials on the Web, a contextual identifier could be a URL like a Web origin (e.g., "https://website.example"), a Web origin with a certain path (e.g., "https://website.example/groups/wind-surfing"), or protocol-defined combination of a URL and a time range, allowing for pseudonyms to be "forgotten" or "rotated" after sufficient time has passed.

Note: Other credential schemes aim to mitigate first-party fraud by limiting the device and software that a holder chooses to engage with, sometimes referred to as "holder binding". With this approach, the holder's own device and software are trusted to be leveraged against them to constrain their behavior. This approach requires device and software allow lists, trust framework management, significant additional protocol security considerations, and ultimately means that the issuer chooses the holder's device and software (or provides them with a list of acceptable options from which they may choose). This has additional side effects, such as centralizing and vendor lock-in effects on the marketplace of devices and software. Finally, with this approach, it also only takes a single dishonest holder to thwart the protections of the device or software (that they have physical access to) to re-enable an unlimited number of unlinkable fraudulent presentations of a valid credential in the ecosystem. Catching this behavior after the fact logically requires being able to link presentations once again, one way or another, which would defeat the privacy aims of the scheme.

Overview: BBS Signature Bound Pseudonyms

The BBS signature scheme, the foundation for BBS Pseudonyms, is based on a three-party model:

• Signer (also known as issuer): Issues credentials 
• Prover (also known as holder or user): Receives credentials 
• Verifier: Validates proofs

A prover obtains a BBS signature from a signer over a list of BBS messages and presents a BBS proof (a proof of possession of a BBS signature) along with a selectively disclosed subset of the BBS messages to a verifier.

Each BBS proof generated is unlinkable to other BBS proofs derived from the same signature and from the BBS signature itself. If the disclosed subset of BBS messages are not linkable then they cannot be linked by their cryptographic presentation alone.

BBS pseudonyms extend the BBS signature scheme to “bind” a “cryptographic pseudonym” to a BBS signature retaining all the properties of the BBS signature scheme:

1.  A short signature over multiple messages
2. Selective disclosure of a subset of messages from prover to verifier
3. Unlinkable proofs.

In addition BBS pseudonyms provide for:

1. An essentially unique identifier bound to a signature/proof of signature whose linkability is under the control of the prover in conjunction with a verifier or group of verifiers. Such a pseudonym can be used when a prover revisits a verifier to allow a verifier to recognize the prover when they return or for the prover to assert their pseudonymous identity when visiting a verifier
2. Assurance of per-signer uniqueness, i.e., the signer assures that the pseudonyms that will be guaranteed by the signature have not been used with any other signature issued by the signer (unless a signature is intentionally reissued).
3. The signer cannot track the prover presentations to verifiers based on pseudonym values.
4. Verifiers in separate “pseudonym groups” cannot track prover presentations.

How BBS Pseudonyms Work

Overview

To realize the above feature set we embed a two part pseudonym capability into the BBS signature scheme. The pseudonym’s cryptographic value will be computed from a secret part, which we call the nym_secret and a part that is public or at least shared between the prover and one or more verifiers. The public part we call the context_id. 

A simplified overview of this flow is shown in Figure 3:

Issuance

To bind a pseudonym to a BBS signature we have the signer utilize Blind BBS signatures and essentially sign over a commitment to the nym_secret. Hence only a prover that knows the nym_secret can generate a BBS proof from the signature (and also generate the pseudonym proof).

The prover chooses their (random) prover_nym and commits to it. They then send the commitment along with a ZKP proof that the prover_nym makes this commitment. The signer verifies the commitment to the prover_nym then generates the signer_nym_entropy and “adds” it to the prover_nym during the signature process. Note that this can be done since we sign over the commitment and we know the generator for the commitment.

As in Lysya2000 we are concerned with the possibility of a dishonest user and hence require that that nym_secret = prover_nym + signer_nym_entropy be the sum of two parts where the prover_nym is a prover's secret and only sent to the signer in a blinding and hiding commitment. The signer_nym_entropy is “added” in by the signer during the signing procedure and sent back to the prover along with the signature. 

Verification

The pseudonym is calculated from nym_secret and context_id using discrete exponentiation.

1. nym_secret: A two-part secret combining:
   • prover_nym: Generated and known only by the prover
   • signer_nym_entropy: Contributed by the signer during signature
2. context_id: A public identifier that is shared between the prover and one or more verifiers

This is similar to the computations in Lysya2000 and ABC2014. The pseudonym is presented to the verifier along with a ZKP that the prover knows the nym_secret and uses it and the context_id to compute the pseudonym value. A similar proof mechanism was used in Lysya2000. See chapter 19 of BS2023 for an exposition on these types of ZKPs.

See the appendix for a detailed diagram showing the complete BBS pseudonym issuance and verification flow.

BBS Pseudonym Example Applications

Certifiable Pseudonyms

Certifiable pseudonyms work as follows:  the prover creates unique pseudonyms based on context_ids they choose. While the nym_secret is guaranteed unique to and by the issuer, the issuer never learns its value. 

When using the pseudonym, the prover presents both the context_id and pseudonym to identify themselves, along with any attributes (messages) they choose to reveal. No one else without the nym_secret and signature can produce a proof that they “own” the pseudonym. The prover can create as many different, unlinkable pseudonyms by coming up with different values for the context_id. 

Scope Exclusive Pseudonyms

With scope exclusive pseudonyms, the verifier or group of verifiers require the use of a specific context_id. This allows the verifier (or group of verifiers) to track visits by the prover using this credential/pseudonym. A verifier can limit data collection, i.e. data retention minimization, by periodically changing the context_id since the pseudonyms produced using different context_ids cannot be linked. For example a context_id like “mywebsite.com/17Nov2024” that changes daily means the verifier could only track visits daily.

Scope Exclusive Pseudonyms with Monitoring

Scope exclusive pseudonyms with monitoring enable regulated privacy in scenarios requiring third-party oversight. Consider a system for purchasing controlled chemicals: A prover with appropriate credentials uses a different pseudonym with each vendor. This prevents vendors from colluding on prices or learning secret formulas by tracking a prover's complete purchase history across different vendors. At the same time, for regulatory compliance and public safety, vendors must report all purchases to a monitor, including the pseudonym used and their vendor-specific context_id. The prover shares their nym_secret only with the monitor, allowing the monitor to link different pseudonyms to the same prover when necessary. This separation between nym_secrets and other credential-binding secrets is crucial - it enables regulatory oversight without introducing additional cross-tracking by vendors.

A Short Selection of References

1. [Chaum1985] D. Chaum, “Security without identification: transaction systems to make big brother obsolete,” Commun. ACM, vol. 28, no. 10, pp. 1030–1044, Oct. 1985, doi: 10.1145/4372.4373.
2. [Lysya2000] A. Lysyanskaya, R. L. Rivest, A. Sahai, and S. Wolf, “Pseudonym Systems,” in Selected Areas in Cryptography, vol. 1758, H. Heys and C. Adams, Eds., Lecture Notes in Computer Science, vol. 1758, Berlin, Heidelberg: Springer Berlin Heidelberg, 2000, pp. 184–199, doi: 10.1007/3-540-46513-8_14.
3. [ABC2014] P. Bichsel et al., “D2.2 – Architecture for Attribute-based Credential Technologies – Final Version,” Aug. 2014. [Online]. Available: https://abc4trust.eu/download/Deliverable_D2.2.pdf. [Accessed: Feb. 10, 2025].
4. [BS2023] D. Boneh and V. Shoup, “A Graduate Course in Applied Cryptography,” Version 0.6. [Online]. Available: https://toc.cryptobook.us/book.pdf. [Accessed: Feb. 10, 2025].
5. [IETF-BBSblind-00] Internet Engineering Task Force, “BBS Blind Signatures – draft-irtf-cfrg-bbs-blind-signatures-00,” [Online]. Available: https://www.ietf.org/archive/id/draft-irtf-cfrg-bbs-blind-signatures-00.html#. [Accessed: Feb. 10, 2025].
6. [IETF-BBSlink-00] Internet Engineering Task Force, “BBS Per-Verifier Linkability – draft-irtf-cfrg-bbs-per-verifier-linkability-00,” [Online]. Available: https://www.ietf.org/archive/id/draft-irtf-cfrg-bbs-per-verifier-linkability-00.html#. [Accessed: Feb. 10, 2025].

Appendix: Complete BBS Pseudonym Flow (Issuance & Verification)