I have an alternative approach that I believe is an improvement on the current proposal. The idea is that a user will request a credential, which will be a BBS signature of a verifiable random function (VRF) key.

When the issuer receives an initial request, it will generate a random VRF key k, store it in a database associated with that user, and mint a credential by BBS signing the VRF key k. Then, it will send the VRF key along with the BBS signature down to the user. If the user loses their credential, the issuer can re-sign the k they stored and send a new credential back with the same k.

Relying parties will have a well known identity I which can be used as input to the VRF, and the pseudonym for relying party I will be Y = VRF_k(I). In order to authenticate to the relying party, the user can prove (in zero-knowledge) that there exists k and a valid BBS signature on k by the issuer's public key, and that the VRF was executed correctly. We can include a nonce in this proving process to prevent re-use attacks here, and it is straightforward to intertwine this with the zero-knowledge proof as a label in the Fiat-Shamir transcript.

The relying party can verify the proof, ensure that the identity the proof is related to is its own, and extract the VRF output from the proof directly. The VRF output is a stable pseudonymous identifier which will never change unless the underlying value k changes, so it can be used as a stable identifier for that user in the relying party's systems.

One nice part of this system is that relying parties, even if they collude with one another, cannot discover whether users are the same. Further, each user account only grants one pseudonym in the given service. This way, you can rely on the scarcity of accounts on the issuer as a way of metering the total number of accounts in the relying party coming from that issuer. It is important to note that if the issuer colludes with the relying party, they can de-anonymize the user by manually computing VRF_k(I) on the issuer's servers. We could theoretically make k only known to the user, but this would introduce problems with account recovery: if the user ever forgot their k permanently, they would lose all of their accounts formed in this way. However, if k were only known to the user, then even the issuer could not link the users' various accounts together, or de-anonymize the user.

I have prototyped the cryptography I described above in Rust, and it performs satisfactorily: all of the operations take ~5ms on my MacBook pro. Happy to share that code if there is any interest from the community.