Anonymous credentials and the post-quantum squeeze
The push to post-quantum (PQ) cryptography is not a simple swap. Algorithms like ML-KEM and ML-DSA carry heavier computational and bandwidth costs than RSA or elliptic curves, so they aren't always viable as one-to-one replacements. Progress on the biggest targets is real, though: roughly half of TLS connections to Cloudflare's edge now resist store-now/harvest-later attacks, and PQ certificates are moving toward practical large-scale deployment.
TLS is the easy case, comparatively. Many other cryptographic workloads lack obvious PQ stand-ins. Anonymous credentials (ACs) sit squarely in that camp. ACs let a party prove a claim — say, holding a valid driver's license for three years — without disclosing anything else, like date of birth or address. That selective-disclosure property is attractive for a range of applications, but it hinges on primitives that could be hard to retrofit with quantum-resistant math.
The practical question is whether classical AC constructions have drop-in PQ replacements that survive real-world traffic loads, or whether the applications themselves need redesigning. One demanding scenario makes a useful test case: rate-limiting requests from agentic AI platforms and users. This high-scale use case stresses every part of an AC system and shows, concretely, whether today's PQ research is ready for production.
Where anonymous credentials already appear
AC deployments are still young, but they are no longer experimental. Industry and public-sector pilots have been popping up in recent years, targeting identity, payments and access control. Each deployment so far has built on classical cryptography, mostly pairing-based signatures and zero-knowledge proofs that are efficient in practice but vulnerable to a quantum adversary.
The threat model matters here. An attacker who can harvest today's AC-protected traffic and decrypt it years later creates a long-term privacy exposure, not just a credential-forgery risk. The credentials themselves might be short-lived, but the transcripts and derivable metadata are not. That store-now-decrypt-later reality makes the PQ question urgent even while AC adoption is still in its first wave.
The PQ research landscape for credentials
Cryptographers have begun mapping out what post-quantum ACs could look like. The main lines of work are lattice-based and code-based constructions, plus PQ-friendly zero-knowledge proofs. A central tension keeps recurring: the math behind these schemes is bulkier than what classical ACs use, and the proof sizes and verification costs tend to scale up quickly.
Some recent schemes show promise for structured use cases, where the credential format is restricted and the verifier can tolerate higher latency. Others target the harder problem of fully anonymous, unlinkable credentials under PQ assumptions. The gap between the two is wide, and it is exactly where real deployment decisions will be made.
What bridging the gap looks like
Getting PQ anonymous credentials to production will require more than faster algorithms or smaller proof sizes. It will require changes at the application layer, similar in spirit to what PQ TLS has forced on certificate management. For the rate-limiting scenario, that means deciding how much privacy is worth what performance cost, and whether an unlinkable credential is necessary or whether a linkable-but-anonymous token is sufficient.
The field is closer than it often appears. Recent work has produced PQ-friendly credential schemes that operate within realistic bounds for specific workloads, and the research pipeline keeps tightening the numbers. The remaining work is largely engineering: integrating these schemes into protocols, evaluating them under load, and hardening their implementations.
The likely outcome is not a single universal PQ credential scheme. It is a toolkit — a set of constructions tuned for different trade-offs between privacy, bandwidth and compute — and a set of protocols that let applications choose the right one. The clock on store-now-decrypt-later is ticking, so the time to build that toolkit is now, before ACs reach mass adoption on primitives that will be too expensive to replace later. The fundamentals are within reach; the next step is treating PQ readiness as a design constraint rather than an afterthought.
Post-quantum anonymous credentials: requirements, not just research
Anonymous credentials (ACs) are poised to move from cryptographic theory to mainstream deployment. The European Union's digital identity wallet, slated for 2026, will let citizens present attributes such as a driver's license or proof of age from their phones. The EU's Architecture Reference Framework (ARF) correctly names the core privacy goal—unlinkability, so that multiple presentations of the same attribute cannot be tied to one user. But the framework itself admits its current mitigation is weak: it recommends limited-time attestations, which it says would "only partially mitigate Relying Party linkability." Single-use credentials are dismissed for "complexity and management overhead," leaving organizational and enforcement measures to deter collusion rather than cryptographically guaranteed privacy.
Cryptographic researchers have pointed out that the proper fix is adopting anonymous credentials, but there is a long-term problem: well-studied constructions such as those based on BBS signatures are not quantum-resistant. Some newer schemes are post-quantum unlinkable (privacy holds even against quantum adversaries), but they are still forgeable. And deployment is not simply a matter of picking a new algorithm: in the EU, only primitives listed in the SOG-IS catalogue can be used, and that catalogue currently stops at RSA and ECDSA, leaving post-quantum cryptography unaddressed.
The EU's own roadmap flags post-quantum transitions for high-risk use cases as soon as 2030. The first wallet deployment will not be quantum-secure, but research into a post-quantum anonymous credential alternative is already critical. The US is moving too: digital IDs have been usable at TSA checkpoints since 2024, and the Department of Homeland Security has funded six privacy-preserving digital credential wallets and verifiers.
At the IETF, standardization efforts are underway. Active drafts like Longfellow and Anonymous Credit Tokens (ACT), plus adopted drafts such as Anonymous Rate-limited Credentials (ARC), propose more flexible multi-show anonymous credentials. Post-quantum anonymous credentials were flagged as a research opportunity at IETF 117 in 2023.
What a real-world AC must do
For practical deployment, it helps to think of an anonymous credential as a refined blind signature. A blind signature has two phases: issuance, where a server signs a client-chosen message, and presentation, where the client reveals the message and signature. The scheme must be unlinkable (the server can't match a presentation to its issuance run) and unforgeable (no client can produce a valid signature without the server).
ACs extend this by letting the client reveal only part of the message during presentation. The message itself typically has three parts:
- Private state, such as a counter tracking how many times the credential was used. The client proves the state is valid—say, a counter between 0 and N—without revealing its value. In rate limiting, this is the number of requests remaining.
- A nullifier: a random value revealed at presentation that stops a user from spending the same credential twice.
- Public attributes known to both sides, binding the credential to a context like a validity window without exposing the exact issuance time.
This structure suits rate limiting well. If the limit is 1,000 requests per hour, the client can make on average about 0.27 requests per second before throttling. Rate limits are best enforced per-origin, meaning the client can use the same credential up to the limit at any verifier website, while maintaining unlinkability across all of them.
Several constraints shape the design space. The current IETF-generation ACs are only privately verifiable, meaning the issuer and the verifying origin must share a private key. Many deployments will require public verifiability, where only the issuer's public key is needed—as BBS-based credentials already provide. Round complexity also matters: an AC is round optimal when both issuance and presentation complete in a single HTTP exchange. Some newer papers trade extra rounds for lower bandwidth, but in high-traffic, latency-sensitive environments, round optimality is a hard requirement.
Within those boundaries, the objective is post-quantum ACs with minimal communication cost and runtime, specifically for rate-limiting scenarios.
Why post-quantum credentials can’t be a lift-and-shift
Anonymous credentials (ACs) in use today, such as ARC and ACT, are built on elliptic curves. Their efficiency comes directly from the rich algebraic structure of those curves, but that same structure is exactly what quantum computers threaten. The instinctive fix — swap the elliptic curves for a post-quantum replacement like CSIDH — runs into a hard wall: constructing the required zero-knowledge proofs from isogenies demands a trusted setup, and no algorithm for performing a trusted setup in CSIDH exists. Workarounds exist, such as combining generic multi-party computation techniques with cut-and-choose protocols, but they add significant computational cost to already expensive isogeny operations.
The broader lesson is that post-quantum ACs cannot be a simple component swap. They require new designs built from fundamentally different primitives, such as lattices or hash functions, with different trade-offs baked in from the start.
The cryptographic toolkit for post-quantum ACs
An anonymous credential system needs to prove statements about secret credential state without revealing it. Several cryptographic paradigms provide the building blocks:
Zero-knowledge proofs
Zero-knowledge proofs (ZKPs) let a prover convince a verifier that a statement is true without revealing the witness. General-purpose systems like STARKs can prove the integrity of any computation up to a certain size. STARKs represent the computational trace as a set of polynomials, commit to them via hash functions, and let the verifier run a quick probabilistic check. Since the proof is just hashes and sampled polynomial values, it is secure against quantum computers.
Cut-and-choose
Cut-and-choose forces honest behavior by having the verifier inspect a random subset of the prover’s work. The prover commits to multiple instances; the verifier picks some to be “cut open” and checked. If the revealed subset is correct, the rest is likely correct too. The technique is a cautionary case study: practical attacks have succeeded against cut-and-choose schemes built with homomorphic encryption by attacking the algebraic structure of the encoding — not the encryption itself.
Sigma protocols and Fiat-Shamir
Sigma protocols use a three-move structure: the prover sends a commitment, the verifier issues a challenge, and the prover responds in a way that is only possible if they know the secret. In practice, the Fiat-Shamir transformation makes the protocol non-interactive by having the prover derive the challenge from their own commitment. This is the basis of ECDSA and of post-quantum signatures like ML-DSA.
MPC-in-the-head
MPC-in-the-Head (MPCitH) generates zero-knowledge proofs by simulating a multi-party protocol in the prover’s head. The prover simulates each virtual party, commits to the simulations, and the verifier challenges them to open a subset. Since MPC is secure against a dishonest minority, this convinces the verifier without leaking the secret. MPCitH builds security from symmetric-key primitives, requires no trusted setup, and often has faster prover times than STARKs for many computations. Its trade-off is that proofs grow linearly with circuit size, while STARKs are succinct.
Rejection sampling
Rejection sampling corrects biased randomness sources or keeps outputs in a desired range. Rather than calling a random generator repeatedly, an efficient implementation uses an eXtendable Output Function (XOF), such as the SHAKE family from the SHA3 standard or the round-reduced TurboSHAKE. By requesting several bytes of output at once — or splitting bytes into nibbles — you can batch queries and find usable in-range values with high probability in a single call.
Generic constructions: a functional baseline
Cloudflare’s 2023 post-quantum Privacy Pass construction is a generic scheme that composes a digital signature with a general-purpose ZKP system. Its modularity is attractive: components can be swapped, and security guarantees follow directly from the underlying parts. The experimental implementation pairs a modified ML-DSA with STARKs, swapping SHA3 for the ZK-friendly Poseidon hash to get a significant speedup.
But the modularity carries a clear cost. A fast 300 ms proof generation requires a 173 kB signature; slowing to 4.8 s cuts the signature nearly in half. A balanced benchmark parameter set signs in 660 ms with a 112 kB signature. For a real-time rate limiting system, the 660 ms issuance time is a strong argument for dedicated constructions that sacrifice some modularity for performance.
Lattice-based approaches
Lattices are a natural candidate: NIST standardized ML-DSA and ML-KEM from them, and an alternative signature like FN-DSA is also lattice-based. Explicit lattice-based AC schemes exist, but the trade-offs are serious. One recent scheme sacrifices round-optimality for smaller communication size, which is unacceptable for latency-sensitive services — with round-trip times of 100 ms or less, each extra round adds noticeable delay. Combined with final credential sizes still over 100 kB, such designs are hard to justify.
Hash-and-sign and its blind-signature problem
Lattice blind signatures built on hash-and-sign face a fundamental security issue. If the user can request signatures on arbitrary points, they can reconstruct a short basis from the responses — equivalent to key recovery. The standard defense requires the user to prove in zero-knowledge that the requested point is the blinded output of the specified hash function. Proving hash preimages in a ZKP, however, is expensive: conventional hashes like SHA3 do not fit efficiently inside proof systems.
State-of-the-art lattice blind signatures focus on minimizing final signature size — around 22 kB, or 48 kB for a privately-verifiable protocol — but push the cost into issuance. By the authors’ own analysis, the required ZKPs for hash and lattice relations add several hundred kilobytes and take 20 seconds to generate and 10 seconds to verify. For large-scale systems, a design that modestly increases signature size in exchange for lightweight issuance would be far more practical.
Hash-and-sign with aborts
A more promising direction combines hash-and-sign with Fiat-Shamir with aborts, the rejection-sampling approach used in ML-DSA. The signature scheme Phoenix builds on this idea, hashing the message into a lattice and using rejection sampling to break the statistical link between signature and private key.
An anonymous credential scheme built on this foundation avoids costly hash-preimage proofs: instead of proving hash validity, the user commits to their attributes directly. That yields substantial gains. Credentials with attribute proofs come in just under 80 kB, with signatures under 7 kB. Issuance takes less than 400 ms, and showing a credential about 500 ms. The implementation supports proving relations between attributes and requesting pseudonyms for different instances.
With a proof of knowledge of a signature at 40 kB and prover time under a second, this scheme stands out as a strong contender. It would still need a significant speedup for real-time use, but recent advances in lattice samplers suggest improvement is plausible.
MPC-in-the-head: the VOLEitH direction
VOLE-in-the-Head (VOLEitH) builds ZKPs from Vector Oblivious Linear Evaluation. A VOLE correlation acts as a cryptographic commitment binding the prover, who cannot forge a solution without knowing a secret delta. Because the system is linearly homomorphic, two commitments can be combined — an ideal setup for the commit-and-prove paradigm, where the prover commits to witnesses and proves the circuit gate by gate. Proofs are linear in circuit size, but runtimes are substantially better.
VOLEitH efficiently proves evaluations of symmetric ciphers, which are quantum-resistant. Efficient implementations work over binary and prime fields simultaneously, handling both arithmetic and bitwise operations. Recent work teases blind signatures built on the multivariate signature scheme MAYO with sizes of just 7.5 kB and signing and verification under 50 ms.
VOLEitH is one of several in-the-head approaches in the NIST competition for additional signature schemes. The current literature focuses on high-performance signatures — an explicit full anonymous credential construction using VOLEitH has not yet been proposed. Features standard to ACs, such as multi-show unlinkability or attribute relation proofs, are not yet part of the design, whereas the lattice scheme supports them directly. The general-purpose construction should make adding such features straightforward, and the preliminary performance numbers make this a direction worth watching as cryptanalysis matures.
What still needs to be built
Internship work at Cloudflare focused on identifying the next steps for making anonymous credentials (ACs) Internet-ready. The key takeaway: research must move beyond blind signatures and toward complete, privacy-preserving protocols. These protocols need to combine blind signatures with efficient zero-knowledge proofs and support features like multi-show credentials with internal state. Issuance also needs to be sublinear in communication size relative to the number of presentations.
A 2022 NIST presentation noted that efficient post-quantum secure solutions for anonymous credentials were essentially non-existent. The last three years have produced promising developments in lattice-based and MPC-in-the-head approaches, but efficient post-quantum protocols remain immature. Simply swapping classical building blocks for their quantum-secure counterparts—while essential—is not enough. The field should also design new, post-quantum native protocols rather than only retrofitting old designs.
For the Internet-scale proposals currently under discussion at the IETF, the path forward looks like this:
- ARC (Anonymous Rate-limiting Credentials): A post-quantum construction is conceptually feasible, following structures similar to lattice-based anonymous credentials or the generic post-quantum privacy-pass construction for a reduced-feature version. A critical requirement is per-origin rate-limiting: the ability to transform a token at one origin without linking redemptions across origins. No current post-quantum AC or blind signature scheme supports this. ARC also demands sublinear communication with respect to the number of tokens issued—a property only achieved by hash-and-sign with abort lattices, though "limited shows" are not part of the current ARC proposal. Efficient implementations, especially for blind signatures and zero-knowledge proofs, need real-world testing.
- ACT (Anonymous Credentials with State): This requires all of ARC's properties plus an additional stateful element. Even a simple counter necessitates homomorphic subtraction from a balance within the credential itself, a substantially more complex cryptographic requirement. Post-quantum double-spend prevention that enforces the sequential nature of ACT is also an open research area.
The zero-knowledge bottleneck
Working on ACs quickly surfaces a major performance constraint: efficient zero-knowledge proofs. The specific challenge is proving hash function evaluations inside a ZK circuit. In these circuits, every multiplication operation requires a cryptographic commitment, adding communication overhead. Conversely, XOR and similar operations are nearly free. This asymmetry creates dramatic performance differences; for instance, SHAKE—the primitive underlying ML-DSA—can be orders of magnitude slower inside a ZKP than arithmetization-friendly hash functions.
This is why researchers and implementers are gravitating toward functions like Poseidon or Poseidon2 to speed up their protocols. Ethereum is seriously considering a migration to the Poseidon hash and has called for cryptanalysis, but standardization is nowhere in sight. That absence is a growing problem. Papers increasingly deploy different instantiations of Poseidon, and a steady stream of zero-knowledge-friendly hash functions tailored to specific use cases continues to emerge. The community needs at least one standardized extendable-output function and one hash function for each of a prime field and a binary field, ideally across multiple security levels.
Open questions remain about whether Poseidon is merely the most famous ZK-friendly cipher or genuinely the best one. Its quantum resistance needs scrutiny, as do recently published attacks on round-reduced versions. This challenge sits at the center of a fundamental debate in modern cryptography.
Protocols can be built on well-analyzed standard assumptions, such as the SIS problem on lattices or the collision resistance of SHA3. Pushing efficiency further requires leveraging more algebraic structure, which in turn relies on newer and stronger assumptions. The analysis of novel hash functions occupies the middle ground. For the Internet ecosystem to move forward, confidence is needed in both ends of that spectrum: more research to validate the security of ZK-friendly primitives like Poseidon, and more scrutiny of the stronger assumptions that enable efficient algebraic methods.
A call for post-quantum native design
The cryptographic properties that made classical ACs efficient—most notably the rich structure of elliptic curves—have no direct post-quantum equivalents. The current state of the art spans STARK-based generic compositions, lattice-based schemes, and MPC-in-the-head constructions. The field is full of potential but has no clear winner. Trade-offs among communication cost, computational cost, and protocol rounds remain significant barriers to practical, large-scale deployment when compared with elliptic curve constructions.
To close that gap, future work must produce complete, post-quantum native protocols that address real-world needs. Essential features include per-origin rate-limiting for ARC and stateful credentials for ACT. The missing piece across all these approaches is a set of efficient, standardized, and thoroughly analyzed zero-knowledge-friendly hash functions. Building confidence in these primitives is a prerequisite for enabling efficient post-quantum privacy at scale.
