Which cryptosystem for v0.1 of anonymous credentials ?

[ariard]

Blinded BIP341 Schnorr signatures are vulnerable to Wagner’s attack. While there is a known mitigation it is yet to be evaluate if it fits the Staking Credentials sessions.

Blinded 2-party ECDSA has been studied in Bitcoin context and there is implementation of such protocol.

There is also more complete anonymous credentials based on homomorphic commitment already deployed in Bitcoin context.

[nothingmuch]

Design space

blinded signatures vs. attributes with structure

This is the biggest difference, whether or not tokens can convey more than just a unique unforgeable unit, e.g. homomorphically encrypted amounts.

Blind signature protocols (blind RSA, Schnorr, ECDSA, and e.g. privacyPass) allow the issuer/signer to sign without learning anything about what is being signed. This message is then revealed and used as the nullifier/serial number/unique ID/key image to control double spending.

Anonymous credenital systems like Danake, Coconut and Signal used in WabiSabi (Wagner attack breaks ACL and Brands credentials too) allow the requestor to prove properties of the message being signed in zero knowledge. In Danake and WabiSabi, the signed messages are homomorphic El Gamal/Pedersen commitments to an amount, much like in confidential transactions. A balance proof and range proofs are used to ensure that the amount is valid, without requiring it to be revealed.

In addition to quantitative attributes, qualitative attributes may also be encoded in a way that permits selective disclosure or zero knowledge proofs. In conjunction with unlinkable multi show very flexible policies can be implemented with minimal privacy leaks.

homomorphic values vs unit tokens for e-cash

A system with unit tokens presents several downsides when representing amounts drawn from a fungible pool

1. multiple denominations (e.g. 1-2-5 series or powers of 2) need to be used, which requires O(log(amount)) tokens (exact bound given by Hamming weight in chosen base)
2. each unit is in a different pool each denomination is a different pool
3. reissuance to create tokens for specific payment amount is a potential privacy leak, simple in principle to mitigate e.g. by always having a few of each denomination available ahead of time but hard in practice because hard to model privacy leak and increases crypto & bandwidth costs even more

In comparison, homomorphic values require range proofs at issuance (including when making change from a payment), making the cryptographic cost roughly the same as O(log(amount)) unit tokens or potentially lower for the verifier with more exotic range proofs, the bandwidth cost potentially far lower (bulletproofs/compressed sigma protocols), and the privacy is dramatically improved because the issuer only learns of the net amount spent, so reissuance operations (balance proof with delta of 0, used for joining/splitting amounts, payments etc) are unlinkable and indistinguishable.

public verifiability

When it is appropriate to audit the issuer or when tokens are presented to parties other than the issuer, a publicly verifiable scheme must be used.

In some systems anyone can verify that a token is valid using the issuer's public key, whereas in others only the issuer can verify a token's validity. However In these latter cases auditing should still be possible, since the issuer can create publicly verifiable proofs of acceptance of valid tokens (i know how to do this for WabiSabi and theoretically it should be possible for all with no additional crypto assumptions).

cryptographic primitives

Speaking of cryptographic assumptions,

1. blind RSA

• publicly verifiable variant of privacy pass credentials also uses this

2. bilinear / pairing friendly

• coconut credentials
• threshold issuance blind sigs a la fedimint (BLS IIRC?)

3. prime order abelian group

• secp256k1 (Cashu, WabiSabi)
• NIST P256 (privacy pass)
• Ristretto (Danake, IIRC, did not confirm)

There are papers on other schemes, like Mercurial signatures, though I'm not aware of any implentations.

unlinkable multi show vs. single use

Some systems allow presenting a credential multiple times without these presentations being linkable. Implementing an e-cash like system requires some sort of nullifier, WabiSabi for example uses a DLEQ proof of the randomness in the Pedersen commitment with respect to a seperate generator, and this curve point is the nullifier/serial/unique ID/key image.

epochs

To prune the issuer's storage and to keep redemption cheap, old nullifiers could be discarded by expiring tokens from older epochs. This necessitates a conversion operation, and for privacy only tokens from the latest epoch should be directly redeemable (operations with a non-0 balance proofs), since each epoch is its own separate privacy pool but the same economic pool.

The epochs need to be long enough for clients to not lose their money. The issuer can keep track of this and only expire pools that have a net balance of 0.

I'm not aware of any alternative to this kind of design.

key consistency / tagging attacks

Avoiding tagging attacks, where the issuer partitions clients into separate pools, generally requires more complications, and has occasionally been overlooked. In publicly verifiable schemes this requires clients to all agree on the same key, and only accept tokens issued by that key, and a similar assurance can be made for keyed verification schemes (e.g. cashu, wabisabi) using a proof of valid issuance with respect to an issuer public key.

Additional Related work

Cashu implements a token similar to the non publicly verifiable variant of Privacy Pass tokens on top of secp256k1 in Cashu (IIRC with additive blinding instead of multiplicative, and without the additional HMAC replay/hijacking protection, and DLEQs still WIP)

Danake uses a different algebraic MAC on a different curve than WabiSabi which uses the Signal KVAC scheme is otherwise very similar at crypto level, but is less sophisticated than Danake, which adds bulletproofs, 2-layer wallet structure for lighter weight spending credentials with top up, and epochs due to the tokens being long lived. However, no release has been made and I don't think the project has ever been used. Additionally, WabiSabi (though unfortunately not as implemented) has some theoretical but perhaps meaningful privacy improvements against a global, passive, quantum capable adversary due to the possibility of using perfectly hiding, computationally binding commitments everywhere, whereas Danake relies on computationally hiding commitments during issuance and IIRC adding additional randomness created some difficulties that I was not able to figure out with Danake's credential scheme/algebraic MAC.

Coconut uses pairing crypto to support threshold issuance & public verifiability, and has been applied for Nym for credentials with qualitative attributes and I have also worked out on paper how to do homomorphic values and I believe this was planned for Nym so I think it's possible.

Fedimint uses threshold blind BLS signatures on BLS12-381.

[ariard]

Anonymous credenital systems like Danake, Coconut and Signal used in WabiSabi (Wagner attack breaks ACL and Brands credentials too) allow the requestor to prove properties of the message being signed in zero knowledge. In Danake and WabiSabi, the signed messages are homomorphic El Gamal/Pedersen commitments to an amount, much like in confidential transactions. A balance proof and range proofs are used to ensure that the amount is valid, without requiring it to be revealed.

I think on the long-term anonymous credentials systems where quantitative attributes and qualitative attributes can be negotiated between the Requester and Issuer can open the way to differentiated services (e.g channel liquidity reserves in period of congestion for routing hops) or even enable privacy-preserving re-issuance of credentials when they’re near expiration.

reissuance to create tokens for specific payment amount is a potential privacy leak, simple in principle to mitigate e.g. by always having a few of each denomination available ahead of time but hard in practice because hard to model privacy leak and increases crypto & bandwidth costs even more

There is a trade-off between for unit tokens and their level of expressivity and the fragmentation of the pools. Homomorphic values where everything can be proven in zero-knowledge sounds effectively a huge gain.

When it is appropriate to audit the issuer or when tokens are presented to parties other than the issuer, a publicly verifiable scheme must be used.

Public verifiability is a strong requirement for Staking Credentials, where the Issuer credentials can be verified by N Providers, with minimal interactivity between them (or should delegation be authorized?).

secp256k1 (Cashu, WabiSabi)

Prime order abelian group are well-understood, or at least among the Bitcoin ecosystem. Though BLS signatures are very interesting for non-interactive message aggregation.

Some systems allow presenting a credential multiple times without these presentations being linkable. Implementing an e-cash like system requires some sort of nullifier, WabiSabi for example uses a DLEQ proof of the randomness in the Pedersen commitment with respect to a seperate generator, and this curve point is the nullifier/serial/unique ID/key image.

I think we want single use to prevent credentials re-use and therefore abuse. Another direction can be have to have accountable multi-show, where the server-side decrement state after each show?

To prune the issuer's storage and to keep redemption cheap, old nullifiers could be discarded by expiring tokens from older epochs. This necessitates a conversion operation, and for privacy only tokens from the latest epoch should be directly redeemable (operations with a non-0 balance proofs), since each epoch is its own separate privacy pool but the same economic pool.

I’m not sure if the conversation operation can be done in a trustless and unlinkable fashion for tokens? Ideally the privacy pool would be equal to the economy pool.

Avoiding tagging attacks, where the issuer partitions clients into separate pools, generally requires more complications, and has occasionally been overlooked.

This is where publicity of the Issuer pubkey must be achieve with some guarantee either with gossips or committing in the chain with some notary protocol like Opentimestamps/Mainstay.

[ariard]

There is an implementation of blinded two-party ECDSA available: commerceblock/mercury#418