Post-Quantum Anonymous Credentials Could Bring Privacy-Preserving Web Access
- Cargo
- Machine Learning
- Shipped
- Shipper
- Christopher Patton
- Readers
- 668
MOLE explores issuer-hidden web credentials built with multivariate cryptography, with early designs measured in kilobytes and milliseconds.

Post-quantum web privacy has a practical path forward, but it comes with a bandwidth trade-off. New anonymous credentials based on multivariate cryptography could preserve the privacy properties of today’s Privacy Pass tokens after quantum computers can threaten current signatures. Early designs have promising costs: issuance and presentation data range from 5.4KB to 12.0KB, and each operation takes a few milliseconds in an experimental implementation.
The work centers on MOLE, short for “Moderation Of unLinkable Endorsements,” a proposed framework for credentials that lets services moderate access without learning which trusted issuer vouched for a client. The cryptographic components are still under development, and their security and parameters need further study. But the reported measurements suggest that post-quantum anonymous credentials could be practical enough to move the next phase of work toward protocol engineering.
Privacy Pass separates access from identity
Web services often limit how frequently a client can use a resource. Without privacy-preserving credentials, operators commonly rely on challenges, accounts or fingerprinting to identify traffic. Those mechanisms can add friction or expose information about users. Privacy Pass was designed to reduce that trade-off.
A client receives a set of tokens and later redeems them to access a site. Each token is unlinkable to the client that obtained it, so the service can apply rate limits without tracking a person across issuance and use. Privacy Pass has been deployed for applications such as privacy proxies, including iCloud Private Relay, and relays such as Privacy Gateway.
The protocol relies on classical cryptography, including RSA and elliptic-curve techniques. A sufficiently capable quantum computer could use that cryptography to forge tokens, allowing an attacker to bypass controls such as rate limits. That threat affects whether a token is valid. It does not, by itself, undo Privacy Pass’s privacy guarantee: token issuance and redemption remain unlinkable, even against a quantum attacker.
That distinction creates some breathing room for privacy, while leaving token integrity in need of a post-quantum replacement. The next generation of credentials also aims to support a wider range of clients and more flexible ways to moderate automated traffic. Systems that distinguish clients by type can help operators manage resource use, but they can also reveal more about a client than a particular access decision requires.
MOLE hides which trusted issuer supplied an endorsement
A conventional Privacy Pass token can conceal the client’s identity while still revealing the issuer’s. The verifier needs the issuer’s public key to check the token, so it learns which organization issued it. That can be useful: an issuer’s identity may help a service determine what kind of client is connecting. A token from a customer, for instance, could show that a client may use that customer’s VPN product.
Other decisions only require proof that a trusted party issued a credential. In those cases, identifying the specific issuer offers no necessary benefit and can lead to different treatment for different clients. MOLE is intended to hide the issuer’s identity as well as the client’s, making it harder for a moderator to vary access based on which trusted organization vouched for someone.
The design has three main roles. An anchor issues an endorsement; a moderator accepts endorsements and manages access to a resource; and a client presents an endorsement to the moderator. Before redemption, the client and moderator agree on an anchor set: the public keys of the anchors the moderator trusts. The client then proves that one of those anchors issued its endorsement without disclosing which one.
If the proof is accepted, the moderator issues the client a MOLE credential for interacting with the service. That credential is specific to the moderator, so it does not need the endorsement’s issuer-hiding property or to be verifiable by the public. The framework can therefore accommodate different credential designs, including blind signatures, anonymous credit tokens and anonymous rate-limited credentials.
This split between endorsements and credentials matters for deployment. An endorsement can establish that a client belongs to a trusted group while concealing which member of that group issued it. The moderator can then create a credential suited to its own access rules. The credential could support rate limits or other forms of moderation without exposing the endorsement’s issuer during use.
Post-quantum credentials need reusable building blocks
Post-quantum alternatives are generally larger than classical cryptographic objects. One comparison illustrates the scale: an ML-DSA-44 signature is 2,420 bytes, while an ECDSA-P256 signature is 64 bytes. That gap makes a direct substitution difficult for services that expect compact messages or frequent credential checks.
The challenge for anonymous credentials is broader than finding a single signature scheme. MOLE is meant to support several kinds of credentials, and web services may need to adapt their access controls as traffic patterns change. Building a separate cryptographic design for every use case would limit that flexibility. The goal is a set of building blocks that can be combined into different protocols.
Many post-quantum schemes are tuned for one task. ML-DSA, for example, comes from a wider cryptographic framework, but its parameters are selected to make a digital signature scheme compact and secure. Those same settings are not automatically suitable for other uses. Credential designers cannot assume that a construction which works for signatures will also work safely for anonymous tokens.
Classical credential systems often let protocol designers choose from familiar elliptic-curve tools without having to set the underlying curve parameters themselves. Building efficient post-quantum credentials still demands substantial cryptographic expertise. The research described here aims to make the design space more reusable, so protocol requirements and low-level parameter choices are less tightly coupled.
VOLE-in-the-Head supplies the proof system
One candidate foundation is VOLE-in-the-Head, or VOLEitH, a zero-knowledge proof system introduced by Baum and colleagues in 2023. Zero-knowledge proofs let a prover show that it knows a secret witness satisfying a public statement while keeping the witness hidden. For example, a prover could demonstrate knowledge of an AES key that transforms a public input X into a public output Y, without revealing the key.
That kind of proof can also be turned into a digital signature. In FAEST, the public key consists of X and Y, while the secret key is the AES key K. A signer proves knowledge of K such that Y = AES(K, X). FAEST is a candidate in a signature competition, and its proofs demonstrate that VOLEitH can support practical constructions from symmetric cryptography.
VOLE stands for “Vector Oblivious Linear Evaluation.” In an interactive VOLE process, two parties obtain correlated random values that act somewhat like authentication tags. The verifier uses them to check that a computation involving the hidden witness was carried out correctly. VOLEitH moves this interaction into the prover’s local computation: the prover prepares the values as though both parties had generated them together, commits to them, and uses the Fiat-Shamir transformation to select which parts the verifier checks. The result is a non-interactive proof.
The system’s proofs grow linearly with the size of the witness and the arithmetic work required by the statement. That means VOLEitH is not succinct in the way some other proof systems are. Its advantage is more specific: it can be efficient when a statement can be expressed with equations over small binary fields.
AES offers one example. Many of its operations use arithmetic in GF(28), a field whose elements are single bytes. FAEST proofs for this type of statement are about 4KB using the reported NIST Round 3, 128s parameters. A second example comes from multivariate quadratic, or MQ, problems, where the prover shows knowledge of a solution to a system of quadratic equations over a small field.
KuMQuat is a signature scheme built around an MQ problem. Given a public quadratic map P and its output P(s) for a randomly chosen secret vector s, the challenge is to recover s. The problem is considered hard even for quantum computers. Because the map consists of quadratic equations, VOLEitH can prove knowledge of a solution at relatively low cost. KuMQuat signatures can be as small as 2.6KB.
Those figures do not make VOLEitH signatures smaller than ML-DSA or FN-DSA. The important question for MOLE is whether the same proof machinery can support several credential designs, with manageable costs. Multivariate signature schemes provide another piece of that puzzle.
Multivariate schemes offer small signatures
Unbalanced Oil and Vinegar, or UOV, is a multivariate signature scheme. Its public key is a quadratic map P, and a signature is a vector s that satisfies P(s) = t, where t is derived by hashing and adding a salt to the message.
The signer’s secret key contains a trapdoor that makes it possible to solve the equations. The trapdoor reveals a hidden division of variables into “oil” and “vinegar” groups. Oil variables are never multiplied by one another. Once the vinegar values are fixed, the equations become linear in the oil variables, which the signer can solve. The public map mixes the two groups so that an observer cannot see the structure that makes signing possible.
UOV has one of the smallest signatures among the candidates described: 135 bytes. Its public keys are much larger, at 46.6KB. MAYO is another multivariate candidate, with smaller public keys at the cost of somewhat larger signatures. Both UOV and MAYO use public quadratic maps over small binary fields, making their operations a fit for VOLEitH proofs.
The choice between these designs depends on how credentials are used. A public key can be cached, so a larger key may be acceptable when it is reused often. That can make UOV a useful option for applications where the size of each signature or presentation matters more than the initial cost of distributing and storing the key.
PoMFRIT combines blind signing with VOLEitH
PoMFRIT, published by Baum and colleagues in 2026, combines VOLEitH with the MAYO multivariate signature scheme to produce a post-quantum blind signature. Its reported blind signature size is 6.7KB, with issuance data of a few hundred bytes. Replacing MAYO with UOV can reduce the signature size to 4.3KB, using NIST Round 3 UOV parameters known as uov-Ip and FAEST-EM-128s parameters for VOLEitH. That smaller signature comes with UOV’s larger public key.
Blind signatures let a client obtain a signature without showing the signer the message being signed. A common design begins with a commitment, which hides a message using randomness. The client sends the commitment to the signer, who signs it. The client later proves that it knows both the signature and the randomness used to create the commitment.
In the notation used for this construction, the client chooses a message m and randomness r, then computes a commitment c = H(m, r). The issuer signs c with its secret key and returns the signature s. Because the issuer sees the commitment rather than m, it does not learn the message. To present the credential, the client supplies a zero-knowledge proof that it knows a valid signature and an opening for the commitment.
The issuer sees one object during issuance: the commitment. A verifier later sees a different object: the proof. This separation supports unlinkability, even if the issuer and verifier are the same entity or share information. The issuer cannot match a later presentation to the commitment it signed.
For PoMFRIT, the proof needs to cover the hash used in the commitment and another hash that connects the commitment to the signature. The construction uses the Keccak permutation behind SHAKE and TurboSHAKE. Keccak’s operations map naturally to VOLEitH constraints: XOR is addition, AND is multiplication, and rotations rearrange values. This makes it easier to express than bit-oriented computations in proof systems designed around large prime fields.
Hash evaluation still accounts for much of the proof’s size. PoMFRIT therefore aims to keep the number of Keccak permutations low. In the basic construction, the proof covers two: one for the commitment and one for the signature. In simplified terms, the statement links the signer’s public map and signature to a nested hash of the message, the client’s randomness and a salt chosen by the issuer.
Hiding the anchor extends the blind signature
MOLE endorsements need an additional property. Rather than proving that a particular public key issued a signature, the client must prove that one key in an approved set did so. If the anchor keys are P1 through PN, the proof establishes that there is some index i for which Pi(s) matches the expected hashed value. The index is part of the hidden witness, so the moderator learns that an approved anchor issued the endorsement but not which one.
The researchers report that this can be expressed with roughly the same basic cost as the blind signature: two hashes and one MQ evaluation. The proof needs additional constraints to handle the hidden anchor choice, and the exact circuit design is part of the cryptographic engineering. The same general method could also support other credential types.
Anonymous credit tokens and anonymous rate-limited credentials are among the constructions considered for MOLE. They add requirements such as proving that a credit count lies within an expected range. In VOLEitH, these range checks are described as relatively inexpensive. Across the designs examined so far, hash evaluation remains the main cost, so reducing the amount of hashing could improve several credential types at once.
Proof size and security pull in different directions
Multivariate cryptanalysis remains an active area, and attacks have improved against some parameter choices in recent years. UOV and MAYO have withstood the attacks discussed here, but designers may still need to raise their security parameters as analysis advances. That would add cost to the resulting constructions.
There is also a trade-off between performance and assumptions. In practice, credential systems may accept stronger assumptions about forgery resistance to keep operations efficient. A cryptographic assumption might fail for an anonymous credit token while the same underlying elliptic-curve technology remains secure for ECDSA. The point is not that every use case has the same risk tolerance, but that the security assumptions need to be assessed for each construction.
PoMFRIT reduces proof size by splitting VOLEitH proof generation into stages. First, the client commits to a random mask, hashes the message outside the zero-knowledge circuit, combines the result with the mask and sends a masked target to the issuer. The issuer uses its UOV trapdoor to find a preimage. The client then completes a proof that the preimage is consistent with the earlier commitment.
This arrangement leaves the hash in the protocol, but the issuer can compute it directly as the VOLEitH verifier. The proof does not need to reproduce the hash computation. That saves space, but changes the security assumption. The relevant “one-more-UOV” assumption accounts for the extra information an attacker could obtain through this process. Researchers need to determine whether that information creates a practical route to forgery.
The concern is about token integrity, not privacy. A break in the forgery assumption could let an attacker create valid tokens. It would not give that attacker a way to link a client’s token issuance to redemption. One related result underscores why the distinction matters: researchers at the University of California, San Diego, and INRIA reported forging a 1024-bit RSA signature while using a Privacy Pass issuer as a signing oracle. Privacy Pass uses 2048-bit RSA, along with other defenses, which provides a wider margin. For UOV, a deployment might similarly choose Level 3 parameters instead of Level 1.
These optimizations still need more analysis before systems can rely heavily on them. The size reductions are useful only if the assumptions behind them continue to hold under further study.
Three routes to smaller proofs
One route is to use fewer hash evaluations. PoMFRIT’s staged process removes a hash from the zero-knowledge computation by letting the issuer perform it directly. This benefits proof size, while making the security analysis depend on the one-more-UOV assumption.
A second route is to make each hash cheaper. Standard SHAKE uses a 1600-bit Keccak state and 24 rounds. TurboSHAKE uses 12 rounds, which reduces the work represented in a VOLEitH proof. The researchers say they are comfortable with the resulting security margin.
The Keccak state can also be made smaller. A 256-bit capacity provides 128-bit security and leaves 1344 bits available for the rate. That is more than these constructions need. An 800-bit state leaves a 544-bit rate, which is still sufficient for the reported use. Halving the state reduces the number of multiplications needed in the proof circuit. At the same number of rounds, a smaller state also leaves an attacker with less material to work with.
A third route is to replace conventional hashes with commitments that fit multivariate algebra more directly. One proposed construction uses public random quadratic maps F and G, with a commitment of the form c = (m + F(r), G(r)). Its constraints have the same degree as those used for a UOV signature, potentially shrinking and simplifying the proof by removing symmetric cryptography from the zero-knowledge circuit.
Experiments with this approach produced promising results, but the security of the parameter ranges that improve performance remains unclear. The risk could affect privacy as well as resistance to forgery, so the design needs substantially more study before it can serve as a dependable component.
A related research direction is an MQ-friendly pseudorandom generator. In typical VOLEitH settings, adding one witness bit can add ten bits to a proof. A technique based on a short committed key and a low-degree generator could bring the proof overhead closer to one bit per witness bit. The client would derive a stream from the short key, then include the XOR of each witness bit and its corresponding stream bit in the proof.
The trade-off is more work for the prover, because the generator must be evaluated and witness values begin at degree two instead of one. The proof-size savings also become worthwhile only when the construction contains enough witness bits. A usable generator remains an open design question: a random MQ instance may be too slow, while the very sparse Goldreich generator is at the opposite end of the design space. Intermediate options have received limited study.
Early cost estimates point to protocol engineering
The current development effort includes two proposed schemes: VOLE-IHAT for MOLE endorsements and VOLE-ACT for MOLE credentials. The estimates use UOV uov-Ip, giving each scheme a 46.6KB public key, and FAEST-EM-128s parameters for VOLEitH. The figures are preliminary and may change as the constructions are analyzed.
| Construction | Issuance | Presentation |
| PoMFRIT with UOV | <1KB | 4.3KB redemption |
| VOLE-IHAT | 5.6KB | 6.5KB redemption |
| VOLE-ACT | 5.4KB | 12.0KB spend |
These messages are considerably larger than classical equivalents, which reflects a broad constraint in post-quantum cryptography. The comparison offered for blind signatures is that replacing RSA with PoMFRIT brings overhead comparable to replacing ECDSA with ML-DSA. The prototype implementation reports that each operation takes a few milliseconds. Runtime could be reduced further, at the cost of sending more data.
For a web service, the most visible consequence may be how often a credential must be presented. Classical blind signatures can be inexpensive enough to redeem on every request. With kilobyte-scale presentations, a service may need to amortize one redemption across multiple requests. That introduces protocol questions about how credentials are issued, stored and consumed, alongside the cryptographic work.
The researchers’ view is that the present measurements could shift the effort from designing cryptographic primitives to engineering a workable protocol. Reaching that point still depends on security proofs showing that the schemes hold if UOV is secure, and on further analysis of multivariate cryptography and its parameters.
MOLE’s promise lies in combining two properties: a service can require a trusted credential, while the client’s identity and the specific anchor behind the endorsement remain private. The early costs suggest that this model may fit web applications if systems can handle larger messages and reuse redemptions efficiently. The next milestone is to establish the security assumptions and stabilize the parameters; after that, deployment design will determine where post-quantum anonymous credentials are practical.