Post-Quantum Privacy Passes: Blind Signatures Built on Multivariate Crypto

Most of the post-quantum migration effort has focused on the handshake, and for good reason. Authenticated key agreement in TLS is the foundation everything else sits on, and without it secure communication on the Internet stops working once cryptographically relevant quantum computers exist. But TLS isn't the only place where today's public-key cryptography is doing quiet work. Anonymous access control on the web depends on it too, and that piece is harder to replace.

Why rate limiting is a privacy problem

Site operators need to stop any one client from consuming a disproportionate share of resources. The traditional toolkit for that is unpleasant. CAPTCHAs and other challenges add friction for every visitor. Accounts and fingerprinting identify traffic, but they cost privacy. Users end up choosing between being bothered and being tracked.

Privacy Pass was built to break that tradeoff. A client receives a batch of tokens and spends them later to get access. Each token is unlinkable to the issuance that produced it, so the site can enforce limits without learning which client is which. In practice the user browses as usual, and the operator still gets a usable signal about who is sending traffic.

Cloudflare has run this model for about a decade, in applications such as privacy proxies like iCloud Private Relay and relays like Privacy Gateway. That deployment history matters here because it means the team is designing the successor against real traffic patterns, not hypothetical ones. The next generation is being developed with other collaborators, including Mozilla, and it has two stated aims. The first is better tooling for agentic traffic, meaning automated clients that can consume enough resources to degrade service for human visitors. The second is a more open ecosystem in which more kinds of clients can take part without special arrangements. Neither goal fits inside what Privacy Pass does today.

What quantum breaks, and what it doesn't

The useful part of this analysis is that Privacy Pass is in better shape than a quick reading suggests, and the reason is a split between two properties.

Its authentication layer still relies on classical cryptography, including RSA and elliptic curves. A quantum attacker could therefore forge tokens at will and use them to get past whatever control the site has configured, rate limiting included. That's a real failure, and it's the reason an alternative is needed.

The privacy layer is different. Privacy Pass is unconditionally private, which means no attacker, quantum or otherwise, can link a redeemed token back to its issuance. A quantum computer that can forge tokens still can't tell who spent them. The new capabilities being built for the next generation are designed to keep that same guarantee, so the intent is that an interaction stays private even after Q-day.

That gives the migration some breathing room, but not a lot. Forgery is an operational problem for every site using these tokens, and the replacement has to exist before it's needed. Here's the thing: the research has moved quickly in recent years, but the central obstacle hasn't gone away. Post-quantum primitives are large.

The size problem

The gap is easy to state. ML-DSA-44 signatures run to 2,420 bytes. ECDSA-P256 signatures are 64 bytes. That roughly 38-fold difference is what makes drop-in replacement unrealistic. The team's view is that there's little hope of a direct swap, in the same way it isn't realistic for TLS. The realistic path is to accept primitives with higher costs and then re-engineer the systems around them. Teams in this position usually find that the protocol design, the caching strategy and the amortization of expensive operations matter as much as the raw primitive.

The rest of the piece looks at one candidate future for post-quantum privacy on the web, enabled by a recent advance in blind signature design.

MOLE in brief

The new framework is called MOLE, short for "Moderation Of unLinkable Endorsements." It's worth understanding the vocabulary because the design depends on separating roles that Privacy Pass currently merges.

Privacy Pass is built around a blind signature scheme. A client gets a signature from an issuer's secret key without revealing the message being signed. Later, the client reveals the message and signature, and the issuer can't connect that signature to the earlier issuance. A Privacy Pass token is the message plus the blindly issued signature.

The weakness is that verification needs the issuer's public key, so the verifier learns which issuer produced the token. Tokens protect the client's identity but expose the issuer's. Sometimes that's exactly what's wanted. A token from a particular customer can prove a client is entitled to use that customer's VPN product, and the edge can use that signal in product decisions.

For many use cases, though, the issuer's identity is more than the decision needs. The verifier usually only cares that some trusted entity issued the token. MOLE goes further and hides the issuer entirely, so the verifier can't treat tokens differently depending on who issued them. That enforces equal treatment across client types, which is the mechanism behind the open-ecosystem goal.

The vocabulary works like this. An anchor issues an endorsement. A moderator redeems it. Before redemption, client and moderator agree on an anchor set, the public keys of the anchors the moderator trusts. During redemption, the client proves it holds an endorsement from one of those anchors without saying which one. If the moderator accepts, it issues a MOLE credential that governs the rest of the client's interaction with the site.

Endorsements need one property above all: they must be redeemable without revealing the anchor. Credentials have looser requirements. Because a credential is meant for one moderator, it doesn't need to hide its issuer or even be publicly verifiable. That separation is what makes the framework flexible. Plain blind signatures, anonymous credit tokens, and anonymous rate-limited credentials can all serve as the credential layer.

The real bottleneck: parameter selection

Adaptability and efficiency pull against each other in cryptographic design. A construction tailored tightly to one job is efficient for that job and hard to repurpose. MOLE needs many credential types, and those types will change as web traffic and attacker behavior change. The team needs building blocks that compose into different protocols for different requirements.

Most post-quantum schemes in wide use come from larger mathematical families, and each has been tuned for one application. ML-DSA is the example used here. Its underlying framework could support many constructions, but its parameters were chosen to make the signature compact and secure. Those same parameters wouldn't necessarily be secure for other uses.

That leads to what the team calls the central challenge for post-quantum anonymous credentials: decoupling parameter selection from protocol design. Classical credential systems mostly get this for free. Designers rarely think about the elliptic curve's parameters, which lets non-specialists build useful systems. Designing efficient post-quantum credentials still takes an unusual amount of expertise. A recent development seems to change that picture, and it begins with zero-knowledge proofs.

VOLE-in-the-Head

The story starts with the VOLE-in-the-Head (VOLEitH) zero-knowledge proof system, presented at Crypto 2023. A zero-knowledge proof lets someone show they know a hidden witness that satisfies a public statement, without revealing the witness. A simple example is proving knowledge of an AES key K such that Y = AES(K, X), with X and Y public. Converting that proof into a signature gives a scheme whose security reduces to AES, with X and Y as the public key and K as the secret key. That's the basis of FAEST, a candidate in NIST's ongoing signature competition.

VOLEitH is relatively easy to understand and implement correctly compared with many modern proof systems. VOLE, or Vector Oblivious Linear Evaluation, is an interactive protocol that gives two parties correlated random values. Those correlations act like authentication tags, letting a verifier check that a computation on the hidden witness was carried out correctly. In VOLEitH, the prover simulates locally what the two parties would have generated together, which is where "in the head" comes from. The prover commits to those values, and the Fiat-Shamir transformation picks which parts the verifier checks. That turns the interactive process into a non-interactive proof.

The system isn't succinct in the way some competing proof systems are. Proof size grows linearly with the witness and with the arithmetic complexity of the statement. What makes it useful is that it's concretely efficient for statements expressible as equations over small binary fields. AES qualifies because much of its computation is arithmetic in GF(2⁸), a field whose elements are single bytes. FAEST proofs for that statement come in at about 4KB at NIST Round 3 with the 128s parameters.

KuMQuat is another example. Its signer proves knowledge of a solution to a Multivariate Quadratic (MQ) problem: a system of random quadratic equations over a small field, in which the solver must recover a secret vector s from the public outputs. The problem is believed to be hard even for quantum computers. Since the equations are quadratic, a VOLEitH proof of a solution is comparatively cheap, and KuMQuat signatures get as small as 2.6KB.

Those figures don't look dramatic next to ML-DSA or FN-DSA. But the comparison that matters for MOLE isn't between signature schemes in the same category. MOLE needs a balance between performance and flexibility across many credential types, and VOLEitH alone doesn't provide that. It needs one more ingredient.

Multivariate signatures

The second ingredient is the Unbalanced Oil and Vinegar (UOV) signature scheme, a multivariate design that embeds extra structure into an MQ map. The public key is an MQ map P, and a signature is a vector s satisfying P(s) = t, where t comes from hashing and salting the message.

The secret key is a trapdoor. It reveals a hidden split of each equation's variables into "oil" and "vinegar" groups. Oil variables never multiply each other, so once the vinegar values are fixed, the equations become linear in the oil values and the signer can solve for them. The public key mixes oil and vinegar variables so that the structure stays hidden from everyone else.

UOV is also a candidate in NIST's signature standardization effort. Its signatures are among the smallest in the field, at 135 bytes. The cost is public keys of 46.6KB, which is the largest in the candidate pool. MAYO, another multivariate candidate, goes the other way: much smaller public keys in exchange for slightly larger signatures.

The useful observation is that evaluating a UOV or MAYO signature is about as complex arithmetically as evaluating an MQ instance. Both are public quadratic maps over small binary fields. That makes them a natural fit for VOLEitH, and it's where the breakthrough comes in.

PoMFRIT: a blind signature from VOLEitH and multivariate crypto

Earlier this year, researchers published PoMFRIT, a blind signature scheme presented at USENIX Security 2026. It set what was, at the time, a record for candidate post-quantum constructions: 6.7KB for the blind signature itself and a few hundred bytes for issuance. PoMFRIT is built on VOLEitH and the MAYO multivariate signature.

Swapping MAYO for UOV brings the signature down to 4.3KB. That figure uses NIST Round 3 parameters for UOV (uov-Ip) and FAEST-EM-128s. The trade is a larger public key, which pays off when a key can be cached and used often enough to justify it.

That's competitive with state-of-the-art lattice-based constructions. The more important point is that PoMFRIT's building blocks can be reconfigured into every credential system considered for MOLE, endorsements included.

The mechanics rest on a well-known blind signature pattern. The client seals the message inside a commitment, which in this design is a hash of the message plus client-generated randomness. The signer then signs the commitment directly, without seeing the message. To finish, the client produces a zero-knowledge proof that it knows a signature and the randomness, called the opening, that together verify against the signer's public key. That proof is the blind signature, and anyone holding the issuer's public key and the message can check it.

Written out, the protocol has three steps. The client picks an opening r and sends the commitment c = H(m, r) to the issuer. The issuer produces s = Sign(sk, c) and returns it. The client then produces a proof π of knowledge of s and r satisfying Verify(pk, H(m, r)) = 1. The proof π is the blind signature.

Unlinkability comes from the fact that the client shows completely different objects in each phase. During issuance, the issuer sees a commitment. During presentation, the verifier sees a zero-knowledge proof. Even if the issuer and verifier collude, or are the same entity, they can't connect the two sessions.

The proof size is dominated by the hash evaluation, so the choice of hash matters a great deal. Proof-friendly hashes are not well studied for most proof systems. For VOLEitH, the Keccak permutation behind SHAKE and TurboSHAKE turns out to be a good fit. Keccak's bitwise operations map directly onto VOLEitH constraints: XOR becomes addition, AND becomes multiplication, and rotations just rearrange values. Many popular SNARKs, by contrast, target large prime fields, which makes byte- and bit-oriented operations awkward to express.

Keccak still accounts for most of the VOLEitH proof, so the number of permutations has to be kept to a minimum. PoMFRIT needs two, one for the commitment and one for the signature. The statement being proved is roughly P(s) = H(H(m, r), r_s), where s is the signature, r_s is a salt chosen by the issuer, P is the issuer's UOV public key, and H is the Keccak permutation with output truncated to the required length. Truncation also keeps anyone from inverting the hash.

From blind signatures to endorsements and beyond

An endorsement needs more than a blind signature. It must not reveal which anchor issued it. The verifier now faces a sequence of anchor keys P₁, …, P_N, and the statement becomes P_i(s) = H(H(m, r), r_s) for some anchor key whose index i is part of the hidden witness.

With careful circuit design, that can be written as constraints with roughly the same cost: two hashes and one MQ evaluation. The witness has to prove a little more, and working out exactly what is part of the craft of designing zero-knowledge circuits. The team's view is that this kind of reasoning transfers to almost any modern proof system.

The framework also extends to richer credentials, including the anonymous credit tokens and anonymous rate-limited credentials mentioned earlier. In both cases the main added cost is an extra hash or two. These credentials also need to prove that part of the witness, such as a remaining credit count, falls within an expected range. In VOLEitH, that range check is cheap.

The pattern across every MOLE construction is the same. The main cost is the Keccak evaluation, both its size and how many times it runs. That makes reducing hashing the lever that improves everything at once.

Three levers for cutting cost

Fewer hashes

PoMFRIT's size record came from doing exactly this. The blind signature normally requires proving two hash evaluations, one by the client and one by the issuer. PoMFRIT splits VOLEitH proof generation into two stages. In the first, the client commits to a random mask, hashes the message outside the zero-knowledge circuit, combines the hash with the mask, and sends the masked target to the issuer. The issuer uses the UOV trapdoor to find a preimage of that target. In the second stage, the client proves that the preimage and the earlier mask are consistent. The hash is still part of the protocol, but the issuer, acting as the VOLEitH verifier, can compute it directly instead of the proof reproducing it.

That substantially shrinks the proof, and it also changes the security assumption. Plain UOV assumes no quantum attacker can find a preimage for a random target without the trapdoor. The one-more-UOV assumption, which parallels the one-more-MAYO assumption in the PoMFRIT paper, captures the extra information the attacker sees as a result of this optimization. The working assumption is that this extra information doesn't enable an attack.

Cheaper hashes

Standard SHAKE uses a 1600-bit Keccak state and 24 rounds. Many researchers have come to think 24 rounds is more than necessary, and TurboSHAKE uses 12. That change substantially reduces VOLEitH proof size, and the team says it's comfortable with that margin beyond this application.

Shrinking the state helps too. Of the state, 256 bits are reserved as capacity to reach 128-bit security, which leaves 1344 bits that can be absorbed in one pass. That's more than needed. Halving the state to 800 bits leaves a rate of 544 bits, which is still plenty. At the same round count, the smaller state actually gives more security margin, since an attacker has less to work with. It also halves the multiplications in the circuit, which shrinks the proof.

Multivariate commitments and PRGs

In an ideal setup, the team would skip conventional hashes entirely and use something that composes natively with the algebra of multivariate primitives. Pedersen commitments in elliptic curve cryptography work this way, and the natural question is whether multivariate commitments can be built.

One proposal is to fix public random MQ maps F and G and commit to a message m as c = (m + F(r), G(r)). The constraint degree matches that of the UOV signature, which makes the proof both smaller and simpler, because symmetric cryptography never has to be evaluated inside the zero-knowledge circuit. The team tried this and got some striking results. But it isn't yet clear that the parameter regime where these commitments win is secure, and the risk extends beyond unforgeability to client privacy itself. More study is needed.

A separate idea uses a pseudorandom generator built for low degree. Adding a witness bit normally costs about ten bits of proof under typical VOLEitH parameters. The trick is to commit to a short key and stretch it with a low-degree PRG. Each witness bit w is then stored as w XOR k, where k is a bit from the PRG, so each witness bit costs one bit of proof. The trade-off is that the PRG has to be computed, and witnesses start at degree 2 instead of 1. That mostly hits prover time, and the proof-size benefit only appears once there are a decent number of witness bits. Building a PRG from a random MQ instance works but is very slow and seems overly conservative. The Goldreich PRG sits at the sparse extreme, and the team would prefer something in between, which hasn't received much study yet.

Security caveats the team is taking seriously

Cryptanalysis of multivariate schemes is still relatively young. In the last couple of years, several parameter regimes have fallen to new attacks. UOV and MAYO have held up well so far, and an outright break of either looks less likely each year. Still, the parameters will probably shift in ways that add cost to these constructions.

Credential systems in practice often accept a less conservative posture to gain performance, as long as forgery resistance holds. That usually means leaning on stronger-than-usual computational assumptions. It's possible, for instance, that a pre-quantum attack could break anonymous credit tokens while leaving ECDSA intact, even though both use the same elliptic curve. Those are the kinds of trade-offs that need explicit tracking.

There's also a concrete data point. Researchers at UC San Diego and INRIA forged a 1024-bit RSA signature by using a Privacy Pass issuer as a signing oracle. Privacy Pass itself uses 2048-bit RSA, which, combined with other defenses, leaves a reasonable margin. For UOV, the team is considering NIST Level 3 parameters instead of Level 1. Its conclusion is that the one-more-UOV optimizations need more study before anyone leans on them heavily. It also points out that a break in these assumptions would affect forgery, not client privacy. An attacker who breaks the optimization could mint tokens but still couldn't link a client to its tokens.

The numbers, and what they mean in practice

The team's current cost estimates for the two candidate schemes are below. VOLE-IHAT is a candidate for MOLE endorsements, and VOLE-ACT is a candidate for MOLE credentials. Both use UOV (uov-Ip), so each public key is 46.6KB, and the VOLEitH component uses the FAEST-EM-128s parameters. The team notes these numbers will change as the constructions are analyzed further.

These sizes are much larger than their classical counterparts, which is no surprise. "PQ is big" is the defining feature of this migration. Still, the team's comparison is useful: swapping RSA blind signatures for PoMFRIT carries overhead roughly comparable to replacing ECDSA with ML-DSA. Runtimes are a bright spot. Each operation takes a few milliseconds in the team's implementation, and runtime can be reduced further at the cost of more communication.

If the numbers hold, the migration story changes. The problem moves from cryptographic design to protocol engineering. A classical blind signature might be cheap enough to redeem on every request. A post-quantum one probably won't be, so the real work becomes amortizing a single redemption across multiple requests. That's a systems problem with its own trade-offs around caching, batching, and session design.

What has to happen next

Several steps remain. The protocols need security proofs showing they're secure as long as UOV is secure. The cryptanalysis of UOV has to mature, and the parameters need to settle. The team is explicit that it wants more cryptographers working on multivariate cryptography, because the design space around MQ-friendly commitments and PRGs is largely unexplored.

The payoff is a family of anonymous tokens and credentials that can be composed for different web use cases, with privacy intact after quantum computers arrive. The team's view is that once the parameters stabilize, these schemes will find many applications. Its own word for the current state is that they have only just scratched the surface. The next useful signal will be whether the security proofs hold and whether the amortization work makes the redemption costs tolerable at web scale.