Anonymous credentials the issuer can't trace — no format change, no trusted setup

TL;DR. The digital-identity standards rolling out under eIDAS 2.0 and mobile driver's licenses (SD-JWT VC, ISO mdoc) support selective disclosure, but they are not unlinkable: the issuer's signature is a stable identifier that rides along on every presentation. This post is about making them unlinkable in zero-knowledge — without changing the credential format and without a trusted setup. The key piece is a nullifier that even the issuer cannot trace.

Code: https://github.com/lukasjhan/longfellow · Paper (PDF): https://github.com/lukasjhan/longfellow/blob/main/paper/paper.pdf

Selective disclosure is not unlinkability

The European Digital Identity framework (eIDAS 2.0) obliges member states to issue wallets to every citizen, and U.S. states are rolling out mobile driver's licenses. Two standards dominate this push — IETF SD-JWT VC (JSON/JWS-based) and ISO/IEC 18013-5 mdoc (CBOR-based).

Both advertise selective disclosure: reveal your age, hide your name and address. But there's a trap that fits in one line.

Hiding which attributes you show is not the same as hiding who is showing them.

In both formats the issuer signs a fixed set of salted attribute hashes, and the holder forwards that signature verbatim to every relying party. The signature and the hashes are stable identifiers. Two services that compare notes can tell it's the same person, and the issuer recognizes its own signature anywhere.

A standards body (ETSI) makes the distinction explicit — verifier-unlinkability (relying parties can't correlate) versus issuer-unlinkability (the issuer can't correlate) — and notes that the salted-hash formats provide neither by default. Sixteen cryptographers warned the EU that this design "cannot ensure unlinkability," which eIDAS 2.0 lists as a mandatory requirement. The standard and reality are at odds.

Why the existing fixes fall short

The only mitigation standardized today is batch issuance: the issuer pre-mints many single-use credentials and the holder spends one per presentation. This buys verifier-unlinkability only — the issuer can still correlate — at a recurring cost in issuance, storage, and key management, and it runs out.

The cryptographic alternatives each come with a price.

• BBS#-style anonymous-credential signatures require the issuer to swap out its signature scheme, abandoning the deployed ECDSA credential.

• Groth16-based SNARKs (Crescent, zk-creds, and others) need a per-circuit trusted setup. If the setup is compromised, soundness breaks silently.

Making the SD-JWT VC format that wallets actually ship unlinkable — with no issuer or device changes, and no setup — was an open gap.

The approach: prove possession in zero-knowledge, leaving the credential untouched

The issuer keeps issuing ordinary ECDSA credentials. At presentation, instead of forwarding the credential the holder produces a zero-knowledge proof:

"I hold a valid issuer-signed credential and age_over_18 is true. Nothing else is revealed — to anyone, including the issuer."

This runs in transparent zero-knowledge: no common reference string, no trusted setup, relying only on SHA-256 (Ligero + sumcheck).

That foundation — proving possession of an unmodified ECDSA credential in transparent ZK — is the work of longfellow (Frigo & shelat, Anonymous Credentials from ECDSA, IACR CiC 2024). I build on it. But longfellow targets ISO mdoc only and has no nullifier to prevent linkable repeat use. I add three things.

① Bringing SD-JWT VC into zero-knowledge: the cost of a text format

To verify a credential in zero-knowledge, you have to re-run its verification inside a circuit — base64url decoding, JSON parsing (find the _sd array, check the [salt, "name", value] structure), SHA-256 recomputation, and the issuer's ECDSA signature check.

SD-JWT VC is a text format (JSON + base64url). Unlike mdoc (CBOR, binary), it forces base64 decoding and JSON parsing inside the circuit. I built the first zero-knowledge circuits that parse the SD-JWT VC text format directly, and quantified the cost for the first time:

Text (SD-JWT VC) roughly doubles the in-circuit SHA-256 work relative to binary (mdoc): ~190k vs ~95k hash-circuit inputs.

The closest prior work to target SD-JWT, Mombelli (ETH MSc thesis, 2025), found this in-circuit parsing prohibitive and instead has the issuer re-issue the credential with circuit-friendly primitives. I do the opposite — I verify the genuine SHA-256 _sd digests and the original P-256 signature of an unmodified credential, adding no new cryptographic assumption.

② A blind nullifier the issuer can't trace

A nullifier is a per-context anonymous tag. It enables anonymous duplicate detection — "one vote per election," "one account per service." Present twice in the same context and the same tag N appears, so the verifier catches the duplicate; present in a different context and N is completely different, so the two can't be linked.

Existing nullifiers do this much. The difference here is that even the issuer cannot trace N.

1. At issuance (blind): the holder samples a secret s and a blind r and forms a commitment C = SHA256(s‖r). The issuer simply signs C as an ordinary disclosure (pseudonym_commitment) — it never sees s or r. (Mechanically this is identical to the issuer already signing the holder-binding cnf key: no infrastructure or scheme change.)

2. At presentation: the holder derives N = SHA256(s‖ctx) in zero-knowledge and proves that this N came from the same s the issuer signed inside C.

All the issuer ever saw is the hiding commitment C. Since C leaks nothing about s, the issuer cannot recompute or recognize N later. And because the commitment and the nullifier are both SHA-256, this adds zero new cryptographic assumptions.

The contrast with prior nullifiers is sharp:

• PLUME / Semaphore: there is no issuer at all (a self-held key, or a leaf the admin knows), so "untraceable by the issuer" is vacuous.

• Privacy Pass / ARC: verification uses the issuer's secret key, making the issuer a co-verifier (privately verifiable).

• e-cash: double-spending de-anonymizes the spender.

A nullifier that binds to a standard issuer-signed credential, never de-anonymizes its holder, and is publicly verifiable is — to my knowledge — the first of its kind.

A concrete scenario: anonymous e-voting, and why the issuer is the threat

Anonymous e-voting is where "untraceable even by the issuer" stops being abstract. Voting demands three things at once:

1. Eligibility: only eligible citizens vote.

2. One vote each: no double voting.

3. Anonymity: no one — not even the government — can link a ballot to a voter.

(2) and (3) look like they conflict. Enforcing one-vote-each means you must distinguish voters, and a distinguishing value tied to identity breaks anonymity.

Here is the crux: the adversary you most need to defend against in voting is the government that issued the credential — the issuer. The government issued everyone's credential and knows who holds what. A nullifier the issuer can trace lets the government link ballots to voters. Batch issuance only gives verifier-unlinkability, so the issuer (the government) can still correlate. Without issuer-untraceability, voting anonymity does not hold.

This nullifier solves exactly that. Set ctx = "2025 general election":

• Each voter derives N = SHA256(s‖ctx) in zero-knowledge and attaches it to the ballot.

• A repeated N is rejected as a double vote — one vote each.

• The government only ever saw the hiding commitment C, so it cannot map a ballot's N back to any citizen — anonymous even to the issuer.

• The next election uses a different ctx, yielding a fresh N: ballots don't link across elections, and the voter can vote again next time (the correct behavior).

• Selective disclosure ("citizen, 18+" without revealing identity) and revocation (removing the deceased or ineligible) ride inside the same proof.

Eligibility, duplicate detection, and full anonymity — without trusting the issuer and without extra infrastructure — in a single presentation. The repo ships a demo: npm run scenario:voting-sdjwt.

③ Both formats from one core, plus revocation

The feature blocks — nullifier, revocation — sit on a format-agnostic shared seam (a split-circuit design that MAC-links two circuits). So the new features run unchanged over both SD-JWT VC and ISO mdoc; only the parsing front-end differs (JSON/base64url ↔ CBOR).

Revocation has the authority (CRA) sign the gaps between adjacent revoked IDs, and the holder proves "my ID lies in such a gap" (the mechanism is longfellow's; I extend it to SD-JWT VC). The proof size is constant regardless of the revocation-list size, and it reveals neither the ID nor which gap was used.

Performance

On a commodity desktop (a 2018 AMD Ryzen 7 2700X), every configuration:

Format	Prove	Verify	Proof size
SD-JWT VC	~1.9 s	~0.8 s	~390 KB
ISO mdoc	~1.0 s	~0.45 s	~350 KB

I also measured on a real phone (Galaxy Z Flip5, Snapdragon 8 Gen 2):

• Every configuration proves in under 1.5 s and verifies in under 0.7 s.

• It is 1.3–1.5× faster than the 2018 desktop (a 2023 mobile SoC is simply quicker).

• Peak memory (RSS) is 180–410 MB — identical to the desktop, since it's the proof system's working set rather than a device artifact, and about 5% of the phone's 8 GB.

To remove thermal bias on the phone, I measured the median of seven rounds with the configuration order counterbalanced (rotated each round).

The issuer-untraceable blind nullifier costs under 5% over a plain nullifier, with no change in proof size. Issuer-untraceability is essentially free.

What's new versus what's inherited

• Inherited (longfellow): the transparent ZK proof system, proving an unmodified ECDSA credential, the mdoc circuits, and the signed-range revocation mechanism.

• New here: (1) the first zero-knowledge circuits for the SD-JWT VC text format, and the first quantification of its cost; (2) the first issuer-untraceable blind nullifier bound to a standard credential; (3) unifying both formats and extending revocation to SD-JWT VC.

All of it under the same constraints: no trusted setup, no issuer or device changes, no new cryptographic assumptions.

Closing

Selective-disclosure credentials are shipping without the unlinkability their own governing frameworks require. You can turn them into anonymous credentials in transparent zero-knowledge — leaving the standard untouched, with no trusted setup — and the piece that closes the gap is a nullifier that even the issuer cannot trace. In settings like e-voting, where the issuer itself is the threat, that property isn't a nice-to-have; it's the premise.

• Code: https://github.com/lukasjhan/longfellow

• Paper (PDF): https://github.com/lukasjhan/longfellow/blob/main/paper/paper.pdf

Built on longfellow-zk (Frigo & shelat).