11-19 更新 实时
首页/ 技术栈/ 正文

网络隐私的后量子未来

技术栈 来源:Cloudflare Blog 2026-11-06 22:00 0 阅读 机器翻译
网络隐私的后量子未来

向后量子密码学迁移的最高优先级事项,是诸如 TLS 这类认证密钥协商协议的基本构件。一旦具备密码学意义的量子计算机投入运行,而这些基本构件尚未就位,互联网上的安全通信将无从谈起。然而,如今我们依赖的易受量子攻击的密码学,其应用范围远不止 TLS。

Privacy Pass 是 Cloudflare 等站点运营方用来帮助保护应用免遭滥用的一种协议。我们采用的方式之一,是对单个客户端进行速率限制,使任何单一客户端都不会消耗掉站点过多的资源。通常,这需要用户在摩擦感与隐私损失之间做出某种取舍:用 CAPTCHA 或其他验证手段来调节流量,同时用账号和指纹识别来辨别流量。Privacy Pass 的设计初衷正是为了避免这种在摩擦与隐私之间的取舍。其基本思路是:客户端会获得一定数量的 Token,这些 Token 可被兑换以换取对站点的访问权限。关键在于,每个 Token 都无法与其被签发的客户端关联,从而确保客户端能够在不牺牲隐私的前提下,像以往一样使用站点。

凭借我们积累的 10 年部署经验——将 Privacy Pass 用于隐私代理(如 iCloud Private Relay)和中继(如 Privacy Gateway)等应用——我们正与其他人合作,将这项技术的下一代带到 Web 上。我们的目标之一是开发更精细的工具来管理智能体流量,否则这类流量会消耗过多资源,并降低人类访客的体验性能。另一个目标是通过让更多类型的客户端更容易参与,培育一个更开放的生态。要实现这些目标,就需要在 Privacy Pass 现有能力之外开发新的能力。

考虑到这一发展轨迹,本文探讨抗量子技术的前景。事实上,我们的处境比人们想象的更好。Privacy Pass 目前仍依赖经典密码学,如 RSA 和椭圆曲线。这意味着量子攻击者将能够随意伪造 Token,并利用它们绕过站点运营者想要实施的任何安全机制(例如限流)。另一方面,Privacy Pass 具有无条件隐私性,这意味着任何攻击者,无论是否使用量子计算,都无法将 Token 的兑现与其签发关联起来。更重要的是,我们为这一代新型隐私认证技术所开发的新能力,能够也将会以一种维持同样保证的方式来实现:即使在 Q-day 之后,你的交互依然保持隐私。

这给了我们一点喘息的空间,但我们很快就需要替代方案。这是一个活跃的研究领域,近年来已取得重大进展。不过,正如这场迁移的其他方面一样,主要挑战在于后量子替代方案体量实在太大:ML-DSA-44 签名高达 2,420 字节,而 ECDSA-P256 签名只有 64 字节。而且短期内也别指望能有可直接替换的方案。正如 TLS 那样,我们只能接受代价更高的原语,并重新设计我们的系统来承受这一代价。

但这些原语会是什么呢?在本文中,我们将探讨 Web 上后量子隐私的一种可能未来,它得益于盲签名设计上的一项最新突破。

我们先来概述这项新技术,它目前被称为 MOLE(“Moderation Of unLinkable Endorsements”,即对不可关联背书的审核)。稍后我们会对 MOLE 做更多讨论,但现在先着重介绍与密码学最相关的细节。

Privacy Pass 的核心组件之一是一种盲签名方案,它允许客户端在不向签发方透露所签消息的情况下,获得用签发方私钥签出的签名。之后,客户端可以出示该消息和盲签名,而不会将签名与其签发过程关联起来。

一种 Privacy Pass Token 由消息和盲签发的签名组成。要验证该 Token,验证方需要签发方的公钥,因此必然会得知签发方的身份。所以,这类 Token 虽然保护了客户端的身份,却不保护签发方的身份。

当然,对于某些用例来说,这正是我们想要的。签发者的身份能告诉我们一些信息,即正在连接我们边缘节点的是哪一类客户端,这是我们部分产品和部分客户在决策时所使用的一种信号。例如,客户端可能会使用由我们某个客户签发的 Token,来证明自己有权使用该客户的 VPN 产品。

然而,对于许多用例而言,这些信息超出了我们实际决定是否授予客户端访问某项资源所需的信息量。通常我们只关心这个 Token 是由我们信任的某个实体签发的。事实上,MOLE 更进一步:Token 应当完全隐藏签发者的身份,这样我们就无法根据签发者的不同而对 Token 区别对待。这确保了无论客户端类型如何都能获得同等待遇,也让更多客户端更容易参与进来。

这种隐藏签发者的特性通过一种名为背书(endorsement)的新对象来实现。背书由锚点(anchor)签发,由仲裁者(moderator)兑换。在兑换之前,客户端与仲裁者就锚点集合达成一致,即仲裁者所信任的各个锚点的公钥。在兑换过程中,客户端证明自己获得了锚点集合中某个锚点签发的背书,但不透露是哪一个锚点。兑换被接受后,仲裁者会向客户端签发 MOLE 凭证,并借此管控客户端与该站点的交互。

背书可以有多种形式,但其关键特性在于:它可以在被兑现的同时隐藏签发它的锚点身份。凭证也会有许多类型,但由于它们是供特定的管理员使用,因此无需隐藏锚点,甚至无需可公开验证。这意味着,从盲签名到匿名信用代币,再到匿名限速凭证,都可以用来实例化 MOLE 凭证。

既然我们对要构建的东西已有了概念,接下来看看我们在后量子方面的选择。

在设计密码协议时,适应性与效率往往相互矛盾。有时我们确切知道自己想构建什么,可以为此量身定制一种构造;但协议越是针对这一用例定制,这种构造就越难以适应另一种用例。

对于 MOLE 这样的系统而言,适应性至关重要。我们要构建的不只是一种凭证系统,而是许多种。而且我们所需的凭证类型很可能会随时间变化,尤其是在 Web 上,我们必须不断适应新的流量模式和攻击者行为。为了跟上变化,我们需要一组构建模块,它们可以组合成不同的协议,以满足不同的需求。

如今广泛使用的后量子密码方案大多来自更大的构造族,但都针对其特定应用做了调优。ML-DSA 就是一个很好的例子:衍生出该方案的密码框架可以用来构建各种东西,但为了让 ML-DSA 尽可能紧凑,其参数经过了精心裁剪,以构建一个高效且安全的数字签名方案。然而,同样的参数对其他用例未必安全。

我们已逐渐将此视为后量子匿名凭证的核心挑战:把参数选择与协议设计解耦。经典凭证系统对此习以为常:在大多数情况下,协议设计者无需考虑其所用椭圆曲线的参数,这使得即便不是椭圆曲线密码设计专家的人也能用它构建有用的东西。遗憾的是,设计高效的后量子凭证仍然需要极其庞大的专业知识。

不过,这种情况似乎已经改变。今年早些时候,我们看到了一项突破,它可能意味着匿名凭证的一次根本性转变。

这项突破的根源可以追溯到几年前。我们将从三年前讲起,从 VOLE-in-the-Head(VOLEitH)零知识证明系统(Baum 等人,Crypto 2023)开始。零知识证明系统允许一个人证明自己知道一个隐藏的见证,满足某个公开陈述,同时保持该见证私密。例如,零知识证明可用于证明知道一个 AES 密钥 K,使得 Y=AES(K,X),其中 X、Y 是公开的。该证明可以转换为数字签名,其安全性归约到 AES 的安全性,其中 X、Y 作为公钥,K 作为私钥。这正是 FAEST 数字签名,NIST 正在进行的签名竞赛的候选方案。

原文较长,译文为节选;译文由英文原文机器翻译,术语按行业惯例统一,可在文末展开原文核对。

查看英文原文(The post-quantum future of web privacy)

The highest priorities for the transition to post-quantum cryptography are the basic building blocks of authenticated key-agreement protocols such as TLS. Without these building blocks in place, secure communication on the Internet will not be possible once cryptographically relevant quantum computers come online. However, today we rely on quantum-vulnerable cryptography for much more than TLS.

Privacy Pass is a protocol used by site operators like Cloudflare to help protect applications from abuse. One way we do this is by rate limiting individual clients so that no one client consumes too many of the site's resources. Normally this involves some combination of friction or loss of privacy for users: CAPTCHAs or other challenges to moderate traffic, along with accounts and fingerprinting to identify traffic.Privacy Pass was designed to avoid this tradeoff between friction and privacy. The basic idea is that a client gets issued a number of tokens, which they can redeem in exchange for access to the site. Crucially, each token is unlinkable to the client it was issued to, ensuring the client can use the site as they always had without sacrificing privacy.

With 10 years of deployment experience under our belts — using Privacy Pass for applications such as privacy proxies (like iCloud Private Relay) and relays (like Privacy Gateway) — we, along with others, are collaborating to bring the next generation of this technology to the web. One of our goals is to develop more sophisticated tools for managing agentic traffic that would otherwise consume too many resources and degrade performance for human visitors. Another goal is to foster a more open ecosystem by making it easier for more types of clients to participate. Achieving these goals requires developing new capabilities beyond what Privacy Pass offers today.

Given the trajectory, in this post we look at the prospects for post-quantum. In fact, we're in better shape than one might think. Privacy Pass still relies on classical cryptography, like RSA and elliptic curves. This means that a quantum attacker will be able to forge tokens at will and use them to bypass whatever security mechanism the site operator wants to implement (such as rate limiting). On the other hand, Privacy Pass is unconditionally private, meaning no attacker, quantum or not, can link the redemption of a token to its issuance. What's more, the new capabilities we're developing for this new generation of private authentication technology  can and will be instantiated in a way that upholds the same guarantee: your interaction remains private even after Q-day.

This gives us a little breathing room, but we will need an alternative soon. This is an active area of research that has made significant strides in recent years. Still, just as is the case with other aspects of the transition, the primary challenge is the sheer size of post-quantum alternatives: ML-DSA-44 signatures are a whopping 2,420 bytes, while ECDSA-P256 signatures are just 64 bytes. And there's not much hope for drop-in replacements any time soon. Just as for TLS, we'll have to settle for primitives with higher cost and re-engineer our systems to bear this cost.

But what will those primitives be? In this post, we'll explore one potential future for post-quantum privacy on the web, made possible by a recent breakthrough in the design of blind signatures.

What we need to build: a brief look at MOLE

Let's start with an overview of this new technology, which is presently called MOLE ("Moderation Of unLinkable Endorsements"). We'll have much more to say about MOLE later on, but for now we'll highlight the details that are most relevant to cryptography.

One of the core components of Privacy Pass is a blind signature scheme, which allows a client to obtain a signature under an issuer's secret key without revealing to the issuer the message that it signed. The client can then reveal the message and blind signature later on without linking the signature to its issuance.

One type of Privacy Pass token consists of the message and blindly issued signature. To verify the token, the verifier needs the issuer's public key, and so necessarily learns the identity of the issuer. Thus while these tokens protect the identity of the client, they don't protect the identity of the issuer.

Of course, this is exactly what we want for some use cases. The identity of the issuer tells us something about what type of client is connecting to our edge, a signal we use to make decisions in some of our products and for some of our customers. For instance, a client might use a token issued by one of our customers to prove it is authorized to use the customer's VPN product.

However, for many use cases, this is more information than we actually need to make a decision to grant a client access to a resource. Normally we only care that the token was issued by some entity we trust. In fact, MOLE takes this a step further: the token should hide the identity of the issuer altogether so that we can't treat tokens differently based on who issued them. This guarantees equal treatment regardless of the type of client, making it easier for more clients to participate.

This issuer-hiding property is achieved through a new object called an endorsement. An endorsement is issued by an anchor and redeemed by a moderator. Before redemption, the client and moderator agree on an anchor set, the public keys of the anchors trusted by the moderator. During redemption, the client proves it was issued an endorsement by one of the anchors in the anchor set without revealing which one. Upon acceptance, the moderator issues the client the MOLE credential it will use to moderate the client's interaction with the site.

An endorsement can take many forms, but its key property is that it can be redeemed while hiding the identity of the anchor that issued it. There will also be many types of credentials, but because they're intended to be used by a particular moderator, they needn't be anchor-hiding or even publicly verifiable. This means that everything from blind signatures to anonymous credit tokens or anonymous rate-limited credentials can be used to instantiate MOLE credentials.

Now that we have a sense of what we're building, let's look at our options for post quantum.

A feast of cryptography

When designing cryptographic protocols, adaptability and efficiency are often in tension. Sometimes we know exactly what we want to build and can tailor a construction for that purpose; but the more we tailor the protocol for that use case, the harder it becomes to adapt that construction to a different use case.

Adaptability is essential for a system like MOLE. We're not just building one kind of credential system, but many. And the types of credentials we need are likely to change over time, especially on the web where we must constantly adapt to new traffic patterns and attacker behavior. To keep up, we need a set of building blocks that can be composed together into different protocols to meet different requirements.

Most of the post-quantum cryptographic schemes in wide use today come from larger families of constructions, but have been tuned for their particular application. ML-DSA is a good example here: the cryptographic framework from which this scheme was derived can be used to build a variety of things, but to make ML-DSA as compact as possible, its parameters have been carefully tailored to build an efficient and secure digital signature scheme. However, the same parameters would not necessarily be secure for other use cases.

We have come to view this as the central challenge for post-quantum anonymous credentials: to decouple parameter selection from protocol design. Classical credential systems take this for granted: for the most part, protocol designers don't need to think about the parameters of the elliptic curve they're using, allowing even non-experts in the design of elliptic curve cryptography to build useful things with it. Unfortunately, designing efficient post-quantum credentials still requires an enormous amount of expertise.

This situation seems to have changed, however. Earlier this year, we saw a breakthrough that represents a potential sea change for anonymous credentials.

VOLE-in-the-Head

The roots of this breakthrough go back several years. We'll pick up the story three years ago, with the VOLE-in-the-Head (VOLEitH) zero-knowledge proof system (Baum et al., Crypto 2023). A zero-knowledge proof system allows one to prove knowledge of a hidden witness, satisfying some public statement while keeping the witness private. For example, a zero-knowledge proof can be used to prove knowledge of an AES key K for which Y=AES(K,X), where X,Y  are public. This proof can be transformed into a digital signature whose security reduces to the security of AES, with X,Y as the public key and K as the secret key. This is exactly the FAEST digital signature, a candidate in NIST's ongoing signature competition.

Compared to many contemporary proof systems, VOLEitH is relatively simple to understand and implement securely. VOLE stands for "Vector Oblivious Linear Evaluation" and is an interactive technique that gives two parties correlated random values. These correlations act like authentication tags, allowing the verifier to check that a computation on the hidden witness was performed correctly. In VOLEitH, the prover prepares locally what the two parties would normally generate together — hence “in the head” — then commits to those values and uses the Fiat-Shamir transformation (a widely used tool in cryptography) to select the parts the verifier checks. This step turns the interactive VOLE process into a non-interactive zero-knowledge proof.

Apart from its simplicity, VOLEitH is a fairly unremarkable proof system. It's not succinct in the way many other proof systems are: its proofs are asymptotically linear in the size of the witness and the arithmetic complexity of the statement being proved. However, VOLEitH is concretely very efficient for a particular type of statement, namely one that can be expressed as a set of equations over small binary fields.

One example is the relation Y=AES(K,X) we just discussed. We don't normally think of AES as a set of equations, but many of its computations are designed around arithmetic in GF(28), a field whose elements are single bytes. FAEST proofs for this statement are only about 4KB (NIST Round 3, 128s).

Another example is the KuMQuat signature scheme, in which the signer proves an instance of the Multivariate Quadratic (MQ) problem. Here we're given a system of random, quadratic equations of multiple variables over a small field, like GF(28). Mathematically, this MQ map P looks something like P(s) = (sTA1s + b1s,…,sTAms + bms) where s and each bi are length n vectors and each Ai is an n-by-n matrix. Given P,P(s) for random s, the MQ problem is to find s. We call it quadratic because we multiply the elements of s by itself.

The MQ problem is believed to be hard to solve even for a quantum computer. But because P is made up of quadratic equations, proving knowledge of a solution with VOLEitH is fairly cheap, yielding KuMQuat signatures as small as 2.6KB.

When compared to other post-quantum signatures like ML-DSA or FN-DSA, these numbers don't look especially impressive. But how VOLEitH compares to other schemes in a particular category of constructions is beside the point. For MOLE, we'll need to strike a balance between performance and the ability to build many types of credential systems. To that end, we need one more ingredient.

Multivariate signatures

Another way to build signatures from MQ maps involves embedding some additional mathematical structure into the map. In the Unbalanced Oil and Vinegar (UOV) signature scheme, the public key is an MQ map P, and a signature is a vector s satisfying P(s) = t, where t is obtained by hashing and salting the message to be signed.

The secret key for this signature scheme is a trapdoor for P with which the signer can derive solutions to the MQ equations. The trapdoor reveals to the signer a hidden partitioning of the variables of each quadratic equation into “oil” and “vinegar” variables. Oil variables are never multiplied by one another, so fixing the vinegar values turns the equations into a linear system that the signer can solve for the oil values. In the public key, oil and vinegar variables are mixed together in a way that hides this structure in the map.

UOV is also a candidate in NIST's ongoing signature standardization effort. It has one of the smallest signatures among the candidates, at just 135 bytes. The trade-off is that it has the largest public keys, at 46.6KB. MAYO is another multivariate candidate with much smaller public keys, at the cost of slightly larger signatures.

The key thing to take away here is that the arithmetic complexity of evaluating a UOV (or MAYO) signature is comparable to evaluating an MQ instance. Both are public quadratic maps over small binary fields, making them a good fit for VOLEitH. This brings us to the breakthrough.

Blind signatures from VOLE-in-the-Head and UOV

Earlier this year, a blind signature called PoMFRIT was published (Baum et al., USENIX Security 2026) that achieved what at the time was a record for candidate post-quantum constructions: 6.7KB for the blind signature itself and just a few hundred bytes for issuance. PoMFRIT is based on VOLE-in-the-Head and the MAYO multivariate signature. We can easily drive the size of the signature down to 4.3KB by swapping MAYO out for UOV. (This figure uses NIST round 3 parameters for UOV (uov-Ip) and FAEST-EM-128s.) The trade-off is larger public keys, but this pays off in applications where a public key can be cached and used sufficiently often.

This is competitive with state-of-the-art lattice-based constructions. But the really good news is that building blocks of PoMFRIT can easily be reconfigured into all of the credential systems we've considered for MOLE, including endorsements. More on this in a bit: for now, let's look at how PoMFRIT works in more detail.

A well-known paradigm for designing blind signatures is the following. First, the client places the message in the cryptographic equivalent of a sealed envelope, called a commitment. For our purposes, a commitment is simply the hash of the message together with some randomness generated by the client. To complete issuance, the signer simply signs the commitment directly.

To construct the blind signature, the client produces a zero-knowledge proof of knowledge of the signature and the randomness it used to compute the commitment, called the opening. A verifier would use the signer's public key to verify this proof.

Let's define a bit of notation to make this clearer:

  1. The client generates an opening r and sends a commitment c=H(m,r) to its message m to the issuer.
  2. The issuer produces a signature s=Sign(sk,c) and sends it to the client. It doesn’t learn the message as it’s hidden behind the hash.
  3. Finally, the client produces a proof π of knowledge of s,r for which Verify(pk,H(m,r))=1,

The proof π is the blind signature. It can be verified by any party in possession of the issuer's public key pk and the message m.

Unlinkability comes from the client presenting entirely different objects during the two phases: a commitment is shown to the issuer during issuance, and a zero-knowledge proof is shown to a verifier during presentation. Even if the issuer and verifier collude or are the same entity, they cannot link the sessions.

The size of the proof π is dominated by evaluation of the hash, so we need to choose a hash function that is friendly for our proof system. For most proof systems, such proof-friendly hashes are not well studied, but for VOLEitH it turns out that the Keccak permutation used in SHAKE and TurboSHAKE is a good choice. Keccak’s bitwise operations translate natively into VOLEitH constraints: XOR becomes addition, AND becomes multiplication, and rotations simply rearrange values. (Many popular SNARKs, by contrast, are designed for large prime fields, making byte- and bit-oriented operations less natural to express.)

Nevertheless, Keccak evaluations end up being the largest component of the VOLEitH proof, so we need to make sure we're using only the minimum necessary number of permutations. PoMFRIT requires two: one for the commitment and another for the signature. Concretely, the statement we prove is roughly P(s)=H(H(m,r),rs) where s is the signature, rs is a salt chosen by the issuer, P is the issuer's UOV public key, and H denotes the Keccak permutation with the output truncated to the appropriate length, which also prevents anyone from inverting.

From blind signatures to endorsements and beyond

Recall that for MOLE endorsements, we need something like a blind signature, but one that doesn't reveal the anchor that issued it. That is, we now have a sequence of anchor keys P1,…,PN, and the statement we now want to prove is  Pi(s)=H(H(m,r),rs) for some anchor key Pi whose index i is now part of the hidden witness.

With some care, we can write this as a set of constraints with roughly the same cost: two hashes and one MQ evaluation. We need to prove a bit more about the witness. What exactly? We won't spoil it for you: ZK circuit design is part of the craft of cryptographic engineering that makes it so fun. We'll just say the kind of thinking needed here is transferable to just about any modern proof system you might encounter.

Even more advanced credential systems can be constructed in this framework, including the aforementioned anonymous credit tokens and anonymous rate-limited credentials. In both of these cases, the primary cost is an additional hash or two. Each of these also requires proving that part of the witness (e.g., the credit count) is in some expected range, but this is low cost in VOLEitH.

Indeed, for every construction we have considered so far for MOLE, the primary cost is the size of the Keccak evaluation and how many times we need to evaluate it. This means that finding ways to reduce the amount of hashing yields improvements across the board.

Optimizations

Before we go any further, we need to acknowledge that cryptanalysis of multivariate cryptography is still relatively immature. We have seen advances against several parameter regimes in just the last couple of years, Both UOV and MAYO have weathered these attacks well, and an outright break of UOV and even MAYO seems more unlikely with every passing year. But we should at least expect the parameters to change in a way that adds a bit of cost to our constructions.

On the other hand, it's not uncommon for credential systems used in practice to adopt a less-than-conservative security posture for the sake of performance in so far as it affects forgery resistance. This typically means relying on stronger-than-usual computational assumptions. That is, it's possible that a (pre-quantum) attack might come along that breaks anonymous credit tokens, but not ECDSA, despite the fact that they both use the same elliptic curve.

Using fewer hashes

PoMFRIT achieved its size record by doing precisely the same thing. Recall that the blind signature requires proving two hash evaluations, one by the client and the other by the issuer. PoMFRIT observes that VOLEitH proof generation can be split into two stages. In the first stage, the client commits to a random mask. It then hashes the message normally (outside of the ZK circuit), combines the result with the mask, and sends the masked target to the issuer. The issuer uses the UOV trapdoor to find a preimage of this target. In the second stage, the client completes the proof that the preimage and previously committed mask are consistent. The hash remains part of the protocol, but the issuer — acting as the VOLEitH verifier — can compute it directly rather than requiring the zero-knowledge proof to reproduce it.

This strategy substantially reduces proof size, but it also changes our security posture. The plain UOV assumption is that no (quantum) attacker can find a pre-image for a random target without knowledge of the trapdoor. The corresponding one-more-UOV assumption (analogous to the one-more-MAYO assumption in the PoMFRIT paper) neatly captures the additional information available to the attacker as a result of this kind of optimization. The assumption, then, is that this additional information doesn't lead to an attack.

This assumption may turn out to be overly optimistic. Recently, researchers at the University of California, San Diego, and INRIA managed to forge a 1024-bit RSA signature using a Privacy Pass issuer as a signing oracle. Fortunately, Privacy Pass uses 2048-bit RSA, which, in concert with other defense mechanisms, provides a pretty good security margin. Likewise, for UOV we might consider using NIST Level 3 parameters instead of Level 1.

In any case, a bit more study will be required before we rely too heavily on these kinds of optimizations. It's worth emphasizing that a break here would only impact an attacker's ability to forge tokens, not the attacker's ability to violate a client's privacy.

Making each hash cheaper

Standard SHAKE uses a 1600-bit Keccak state with 24 applications of an underlying round function. However, since the SHA-3 standard was published, many have come to believe that 24 rounds is just too much crypto. TurboSHAKE works the same way, except the permutation uses 12 rounds instead of 24. This substantially reduces the size of VOLEitH proofs. In fact, we're quite comfortable with this security margin, and not just for this application.

Another change to Keccak that reduces the proof size is to reduce the size of the state. 256 bits of the state are reserved for the capacity to get 128 bits security. That leaves 1344 bits that can be hashed in one go, which is more than we need. Reducing the state by half to 800 bits leaves us with a rate of 544 bits, which is plenty. On top of that, it even increases the security at the same number of rounds, as an attacker has less to play with. The smaller state means we’re using half the multiplications in our circuit, which reduces the size of the proof.

Leaning into multivariate

In an ideal world, we could avoid proving conventional hashes altogether by replacing each hash with something that composes more natively with the algebraic structure of our primitives. Indeed, those familiar with Pedersen commitments and their use in elliptic curve cryptography may wonder if commitments can be constructed from multivariate cryptography.

This might look something like this: Fix public, random MQ maps F and G and commit to a message m using c=(m+F(r),G(r)). The advantage of this approach is that the degree of the constraints is the same as the degree of the constraints for the UOV signature. Not only does this make the proof smaller, it makes it far simpler, since we avoid evaluating symmetric crypto in ZK altogether.

We experimented with this approach for our application, and it yielded some impressive results. However, it's not at all clear yet if the parameter regime in which multivariate commitments yield an improvement is also secure. Notably, the risk here is not just to unforgeability, but also to client privacy. A lot more study is needed.

Another direction is to build an MQ-friendly pseudorandom generator (PRG).

For typical VOLEitH parameters, adding an extra witness bit adds ten bits to the proof. There is a neat trick to make this a lot cheaper: only one bit of proof per bit of witness! Instead of using VOLEitH directly, we commit to a (relatively) short key. That key we stretch into a larger bitstream using a PRG with low-degree so that it can be computed cheaply in the circuit. Now, to add a witness bit w, we get one extra bit k from the PRG, and store the bit w XOR k in the proof.

There is a performance trade-off: we need to compute the PRG and the witnesses start at degree 2 instead of 1. That especially increases prover time. Also the benefits on proof size only start to pay off when you need a decent number of witness bits.

And of course you need a PRG! You can create a PRG using a random MQ instance, but that’s very slow and seems overly conservative. At the other end is the Goldreich PRG, which can be seen as an as-sparse-as-possible MQ PRG. We’d want something in between, but such PRGs haven’t received much study.

Is MOLE ready for post-quantum?

We already have post-quantum privacy today, so we have some time before we need to have a solution in place, but now is the time to develop alternatives.

Multivariate cryptography looks to be a promising basis for easily building a variety of anonymous tokens and credentials. We're currently developing two schemes in this framework: VOLE-IHAT, a candidate for MOLE endorsements, and VOLE-ACT, a candidate for MOLE credentials. Our current cost estimates for these are shown in the table below. The numbers here are subject to change as we analyze and develop these constructions. We use UOV (uov-Ip) in each case, which means the public keys are all 46.6KB. VOLEitH uses the same parameters as FAEST-EM-128s:

issuance

presentation

PoMFRIT (with UOV)

<1KB

4.3KB (redemption)

VOLE-IHAT

5.6KB

6.5KB (redemption)

VOLE-ACT

5.4KB

12.0KB (spend)


These numbers are significantly larger than their classical counterparts. This comes as no great surprise, as "PQ is big" is really the main hallmark of the transition across the board. However, replacing RSA blind signatures with PoMFRIT has comparable overhead to replacing ECDSA with ML-DSA. The runtimes of these protocols are also excellent: each operation takes just a few milliseconds with our implementation. (Runtime can be improved by quite a bit, though at the cost of higher communication.)

If these numbers hold, then we've already reached an important milestone: the transition to PQ anonymous credentials for the web can now shift from cryptography design to protocol engineering. In other words, we think we can make these numbers work. For example, whereas classical blind signatures might be cheap enough to redeem on every request, we'll have to figure out how to amortize a single redemption over multiple requests.

We have some work to do before we get there. First, we need to make sure our protocols are sound, in particular by producing security proofs for them that show they are secure as long as UOV is secure. Second, we need to wait a bit for cryptanalysis of UOV to catch up. We encourage cryptographers to spend time with multivariate cryptography. Once the parameters stabilize, we believe these schemes will find a place in a ton of useful applications. We've only just scratched the surface so far.

正文保留英文原文,标题与摘要由机器翻译。

本文由采集器自动同步

原文发布于 Cloudflare Blog(The post-quantum future of web privacy),标题、摘要与正文由机器翻译,术语按行业惯例统一,未经人工逐句校订。

阅读原文 ↗