# Post‑Quantum Anonymous Credentials (ACs): Challenges, Opportunities & Next Steps
The Internet is undergoing **one of its most complex transformations** — the migration to [post‑quantum (PQ) cryptography](https://www.cloudflare.com/en-gb/pqc/).
Protecting systems against future quantum adversaries is **not** just a matter of swapping RSA or elliptic curves with PQ alternatives like [ML‑KEM](https://csrc.nist.gov/pubs/fips/203/final) and [ML‑DSA](https://csrc.nist.gov/pubs/fips/204/final). These new algorithms introduce **higher computational and bandwidth costs**, making “drop‑in replacement” unrealistic in many contexts.
Cloudflare reports [steady progress](https://blog.cloudflare.com/pq-2025/) — currently, ~[50% of TLS connections](https://radar.cloudflare.com/adoption-and-usage#post-quantum-encryption) to its edge are resistant to [store‑now / harvest‑later attacks](https://en.wikipedia.org/wiki/Harvest_now,_decrypt_later). Quantum‑safe **authentication** will take longer, since it requires large changes in certificate handling. This year saw a [major step forward](https://blog.cloudflare.com/bootstrap-mtc/) toward TLS deployments with PQ certificates.
But TLS is just **low‑hanging fruit** — many other cryptographic applications are harder to transition. One such area: **Anonymous Credentials (ACs)**.
---
## Anonymous Credentials in Context
Anonymous Credentials solve a **privacy dilemma** — proving a fact (e.g., “has held a driver’s licence for >3 years”) **without** revealing unrelated personal details (e.g., date of birth).
Real‑world challenge:
- **Drop‑in PQ replacements** for existing AC primitives don’t yet exist.
- PQ designs may require **re‑architecting applications** to cope with performance costs.
In this post, we explore:
1. **Current AC adoption** — private & public sector.
2. **PQ research directions**.
3. **Bridging theory & deployment** — using a demanding use case: [rate‑limiting requests](https://blog.cloudflare.com/private-rate-limiting/) from AI agents.
---
## Real‑World (Classical) AC Use Cases
### EU Digital Identity Wallet
Planned launch: **2026**
Capabilities:
- Digital verification of attributes.
- Privacy‑preserving age verification ([example](https://educatedguesswork.org/posts/age-verification-id/)).
Privacy goal: **unlinkability** — preventing correlation between multiple credential presentations.
Current challenges:
- Attestations embed immutable identifiers (hashes, public keys, signatures).
- Partial mitigations via *time‑limited attestations*.
- **Single‑use credentials** not yet considered (complexity issues).
- Reliance on **organizational measures** against collusion rather than stronger crypto.
---
### Cloudflare Use Case
Focus:
- Rate‑limiting bots & human traffic ([Privacy Pass](https://blog.cloudflare.com/privacy-pass-standard/)).
- Infrastructure scale: massive, real‑time traffic.
---
### Deployment Examples
- **US digital IDs** usable at TSA since 2024 ([source](https://www.tsa.gov/digital-id/participating-states)).
- DHS funding for **privacy‑preserving wallets & verifiers** ([link](https://www.dhs.gov/science-and-technology/privacy-preserving-digital-credential-wallets-verifiers)).
---
## Requirements for AC Systems
Anonymous Credential ≈ advanced [**blind signature**](https://en.wikipedia.org/wiki/Blind_signature):
**Properties:**
- **Unlinkable** — no correlation between issuance & presentation.
- **Unforgeable** — valid only if issued by the server.
**Message Structure:**
- **Private State** — secret value with zero‑knowledge property validation.
- **Nullifier** — random value to prevent double use.
- **Attributes** — public, contextual fields.
**Technical Goals:**
- **Per‑origin rate limits** without breaking unlinkability.
- **Round‑optimality** — issuance/presentation in one HTTP request‑response.
- **Public verifiability** (e.g., via BBS‑based credentials).
---
## Cryptographic Building Blocks
### Zero‑Knowledge Proofs (ZKPs)
- Prove statements **without revealing secrets**.
- Examples: [STARKs](https://eprint.iacr.org/2018/046) — PQ‑resistant.
### Cut‑and‑Choose
- Verify random subset of committed computations.
- Catch cheating with high probability.
### Sigma Protocols
- Commitment → Challenge → Response flow.
- Non‑interactive via [Fiat‑Shamir](https://link.springer.com/content/pdf/10.1007/3-540-47721-7_12.pdf).
### MPC‑in‑the‑Head (MPCitH)
- Simulate multi‑party protocol internally.
- Commit, challenge, reveal subset.
### Rejection Sampling
- Generate values within range; reject invalid outputs.
- Optimized with XOFs (e.g., **SHAKE**, **TurboSHAKE**).
---
## Building PQ ACs: Approaches
### Challenge — No Simple “Lift & Shift”
- Classical ACs exploit elliptic curve algebraic structures.
- PQ counterparts (lattices, hash‑based) differ significantly.
- Designs must address **ZKP efficiency bottlenecks**.
---
### Approach 1 — **Generic Composition**
- Combine PQ signatures (ML‑DSA) + ZKPs (STARKs).
- Pros: modular, flexible.
- Cons: large signatures (~112 kB), high latency (~660 ms).
### Approach 2 — **Lattice: Hash‑and‑Sign**
- Avoids large proofs, but vulnerable to trapdoor extraction unless combined with ZKPs.
### Approach 3 — **Hash‑and‑Sign with Aborts**
- Use rejection sampling to protect private key.
- Example: [Phoenix signature](https://eprint.iacr.org/2014/1027).
- Implemented PQ AC: ~80 KB credentials, <1 s operation.
### Approach 4 — **MPCitH / VOLEitH**
- Efficient evaluation of symmetric ciphers.
- Proofs scale linearly with circuit size.
- Potential: <50 ms runtime, small signatures (~7.5 kB).
- Limitation: not yet full AC systems.
---
## Comparative Summary
| Method | Pros | Cons | Viability |
| --- | --- | --- | --- |
| Generic PQ Privacy Pass | Flexible | Large, slow | Low |
| Hash‑and‑Sign | Small | Slow issuance, big proofs | Low/Medium |
| Hash‑and‑Sign + Aborts | Balanced size/perf | ~1s runtime | Medium |
| VOLEitH | Fast, small proofs | Lacks full AC features | Medium |
---
## Closing the Gap
**Needed for Real‑World PQ ACs:**
- **Complete privacy‑preserving protocols** combining:
- Blind signatures
- Efficient ZKPs
- Stateful credentials
- Sublinear issuance comms
**ARC Requirements:**
- Per‑origin rate limits
- Sublinear communication wrt token count
**ACT Requirements:**
- Stateful decrementable counters
- PQ double‑spend prevention
---
## Bottleneck: ZK‑Friendly Hash Functions
Performance depends on hash choice inside ZKPs:
- SHAKE → slow
- [Poseidon](https://eprint.iacr.org/2019/458), [Poseidon2](https://eprint.iacr.org/2023/323) → efficient
Need:
- **Standardization & cryptanalysis** for ZK‑friendly hashes.
- Selection of XOF + fixed‑length hash for prime & binary fields.
---
## Conclusion
Post‑Quantum ACs **cannot** be simple replacements of classical systems.
We must build **native PQ protocols** matching demands of Internet‑scale deployment.
**Core Features to Deliver:**
- Per‑origin rate limiting (ARC)
- Complex state handling (ACT)
- Efficient ZKPs with standardized primitives
- Scalability without sacrificing privacy
---
### Call to Action
If you build, deploy or design credential systems:
**Collaborate now** to ensure privacy and security persist in the PQ era.
We’re hiring **1,111 interns** over the next year.
---
> **Side note — AI‑Driven Collaboration:**
Open‑source platforms like [AiToEarn官网](https://aitoearn.ai/) show how multi‑platform AI content generation, publishing, and analytics can accelerate innovation adoption — mirroring the collaboration needed for PQ AC development.
---
