向后量子时代的网络隐私

向后量子密码学的过渡最高优先级是诸如TLS的身份验证密钥协商协议的基本构建模块。没有这些基本构建模块，一旦密码学相关的量子计算机上线，互联网上的安全通信将无法实现。然而，今天我们依赖量子易受攻击的密码学，其用途远不止TLS。

隐私通行证 是一种由Cloudflare等网站运营商使用的协议，用于帮助保护应用程序免遭滥用。我们这样做的一种方式是通过速率限制单个客户端，以便没有任何客户端消耗过多的站点资源。通常这涉及到一些用户摩擦或隐私损失的组合：使用验证码或其他挑战来调节流量，以及使用帐户和指纹识别来识别流量。隐私通行证的设计是为了避免摩擦和隐私之间的权衡。基本思想是，客户端会获得一些令牌，他们可以用这些令牌兑换网站的访问权限。至关重要的是，每个令牌都与它被发放给客户端的链接 是不相关的，确保客户端可以像他们一直以来的方式一样使用该网站，而不会牺牲隐私。

凭借10年的部署经验——使用隐私通行证为隐私代理（如iCloud Private Relay）和代理（如隐私网关）等应用程序——我们与其他人一起，正在合作将这项技术的下一代带到网上。我们的目标之一是开发更复杂的工具来管理代理流量，否则这些流量会消耗过多资源并降低人类访客的性能。另一个目标是通过使更多类型的客户端更容易参与来培养更开放的生态系统。实现这些目标需要开发隐私通行证今天所提供之外的新功能。

鉴于这一趋势，在本篇中，我们探讨了后量子密码学的前景。事实上，我们的情况比人们想象的要好。隐私通行证仍然依赖于经典密码学，如RSA和椭圆曲线。这意味着量子攻击者将能够随心所欲地伪造令牌，并使用它们来绕过网站运营商想要实施的任何安全机制（例如速率限制）。另一方面，隐私通行证是无条件的隐私，这意味着无论攻击者是量子攻击者还是非量子攻击者，都无法将令牌的兑换与其发行联系起来。更重要的是，我们正在为这一代私有的身份验证技术开发的新功能将并以同样的保证来实现：即使在Q日之后，您的交互仍然是私密的。

这给了我们一点喘息的空间，但我们很快就需要一个替代方案。这是一个活跃的研究领域，近年来取得了重大进展。然而，与其他过渡方面的情况一样，主要挑战是后量子替代方案的巨大规模：ML-DSA-44签名高达2,420字节，而ECDSA-P256签名仅为64字节。而且，在不久的将来，对于即插即用的替代方案并没有太大的希望。就像TLS一样，我们将不得不接受 成本更高的原语，并重新设计我们的系统来承担这种成本。

但是这些原语会是什么？在这篇文章中，我们将探讨一个潜在的、通过最近在盲签名设计方面的突破而实现的、后量子网络隐私的未来。

我们需要构建的：MOLE的简要概述

让我们先概述这项新技术，目前称之为MOLE （“无链接端orsement的调节”）。我们之后会更多地谈论MOLE，但目前我们将重点介绍与密码学最相关的细节。

Privacy Pass的核心组件之一是一种盲签名 方案，它允许客户端在发行方的密钥下获得签名，而无需向发行方透露其签名的消息。然后，客户端可以在稍后揭示消息和盲签名，而无需将其与签发链接。

Privacy Pass令牌的一种类型包括消息和盲签发的签名。为了验证令牌，验证者需要发行方的公钥，因此必然会了解到发行方的身份。因此，虽然这些令牌保护了客户端的身份，但它们不保护发行方的身份。

当然，对于某些用例来说，这正是我们所需要的。发行方的身份告诉我们有关连接到我们边缘的客户端类型的一些信息，这是我们用于某些产品和某些客户决策的信号。例如，客户端可以使用我们客户签发的令牌来证明其有权使用客户的VPN产品。

然而，对于许多用例，这比我们实际需要的信息要多，才能做出决定授予客户端访问资源的权限。通常我们只关心令牌是由我们信任的某个 实体签发的。事实上，MOLE更进一步：令牌应该隐藏 发行方的身份，以便我们不能 根据发行方不同而区别对待令牌。这保证了无论客户端类型如何，都能得到平等对待，从而更容易让更多客户端参与。

这种发行方隐藏特性是通过一个称为端orsement 的新对象实现的。端orsement由一个锚 签发，并由一个调节者 兑付。在兑付之前，客户端和调节者就一个锚点集达成一致，即调节者信任的锚点的公钥。在兑付期间，客户端证明它是由锚点集中锚点之一 签发的端orsement，而无需透露是哪一个。在接收后，调节者向客户端发放MOLE 凭证 ，客户端将使用它来调节与网站的交互。

端orsement可以有多种形式，但其关键特性是可以在隐藏签发它的锚点身份的同时进行兑付。也将有许多类型的凭证，但由于它们是为特定的调节者设计的，因此不必隐藏锚点或公开可验证。这意味着从盲签名到匿名信用令牌 或匿名速率限制凭证 都可以用来实例化MOLE凭证。

现在我们已经了解了我们要构建的内容，让我们看看后量子时代的选项。

密码学的盛宴

在设计密码学协议时，适应性和效率往往是相互矛盾的。有时我们确切知道要构建什么，并能为其量身定制一个方案；但随着我们为特定用例定制协议越多，将其构建适应不同用例就越困难。

对于像 MOLE 这样的系统，适应性至关重要。我们不仅仅在构建一种类型的凭证系统，而是多种。而且，我们需要凭证的类型可能会随着时间的推移而改变，特别是在网络上，我们必须不断适应新的流量模式和攻击者的行为。为了跟上步伐，我们需要一套可以组合成不同协议以满足不同需求的构建模块。

今天广泛使用的许多后量子密码方案都来自更大的构造系列，但已针对其特定应用进行了调整。ML-DSA 是一个很好的例子：这个方案所衍生出的密码框架可以用来构建各种东西，但要使 ML-DSA 尽可能紧凑，其参数已被仔细调整以构建一个高效安全的数字签名方案。然而，相同的参数不一定适用于其他用例。

我们已将此视为后量子匿名凭证的核心挑战：将参数选择与协议设计分离。经典凭证系统对此习以为常：在很大程度上，协议设计者无需考虑他们所使用的椭圆曲线的参数，这使得即使是椭圆曲线密码学的设计非专家也能用它构建有用的事物。不幸的是，设计高效的后量子凭证仍然需要大量的专业知识。

然而，这种情况似乎已经改变。今年早些时候，我们看到了一个突破 ，这可能代表着匿名凭证的潜在海变。

VOLE 在脑中

这一突破的根源可以追溯到几年前。我们将故事从三年前开始，当时是 VOLE 在脑中（VOLEitH）零知识证明系统（Baum 等人，Crypto 2023）。零知识证明系统允许一个人证明对隐藏的证人的知识，同时满足某个公开声明而保持证人私密。例如，零知识证明可以用来证明对 AES 密钥 K 的知识，对于 Y=AES(K,X)，其中 X,Y 是公开的。这个证明可以转换成一个数字签名，其安全性降低到 AES 的安全性，X,Y 作为公钥，K 作为私钥。这正是 FAEST 数字签名，是 NIST 正在进行的签名竞赛 的一个候选者。

与许多当代证明系统相比，VOLEitH 相对容易理解和安全地实现。VOLE 代表 "向量 oblivious 线性评估"，是一种交互式技术，为两个参与方提供相关的随机值。这些相关性类似于认证标签，允许验证者检查对隐藏证人的计算是否正确执行。在 VOLEitH 中，证明者本地准备两个参与方通常会一起生成的值——因此称为“在头脑中”——然后对这些值进行承诺，并使用 Fiat-Shamir 变换（密码学中广泛使用的一个工具）来选择验证者检查的部分。这一步将交互式 VOLE 过程转换为非交互式零知识证明。

除了其简单性之外，VOLEitH 是一个相当不显眼的证明系统。它不像许多其他证明系统那样简洁：其证明在证人的大小和被证明陈述的算术复杂度上呈渐近线性。然而，VOLEitH 对于特定类型的陈述非常高效，这种陈述可以表示为小二元域上的一组方程。

一个例子是我们刚刚讨论的关系 Y=AES(K,X)。我们通常不把 AES 看作是一组方程，但它的许多计算都是围绕 GF(2⁸) 中的算术设计的，GF(2⁸) 是一个其元素为单个字节的域。对于这个陈述的 FAEST 证明大约只有 4KB (NIST 第三轮，128 位)。

另一个例子是 KuMQuat 签名方案，其中签名者证明多元二次 (MQ) 问题的实例。在这里，我们得到一个关于多个变量的小域上的随机二次方程组，例如 GF(2⁸)。从数学上讲，这个 MQ 映射 P 看起来像 P(s) = (s^TA₁s + b₁s,…,s^TA_ms + b_ms)，其中 s 和每个 b_i 是长度为 n 的向量，每个 A_i 是一个 n-by-n 矩阵。给定 P,P(s) 对于随机 s，MQ 问题是找到 s。我们称之为二次，因为我们把 s 的元素乘以它自己。

MQ 问题被认为即使对于量子计算机也很难解决。但由于 P 是由二次方程组成的，使用 VOLEitH 证明解决方案的知识相对便宜，产生 KuMQuat 签名的大小最小为 2.6KB。

与其他后量子签名如 ML-DSA 或 FN-DSA 相比，这些数字看起来并不特别引人注目。但是 VOLEitH 与其他方案在特定类别构造中的比较无关紧要。对于 MOLE，我们需要在性能和构建多种类型的凭证系统的能力之间取得平衡。为此，我们需要一个更多元素。

多元签名

从 MQ 映射构建签名的一种另一种方法是将一些额外的数学结构嵌入映射中。在 不平衡油和醋 (UOV) 签名方案中，公钥是一个 MQ 映射 P，签名是一个向量 s 满足 P(s) = t，其中 t 是通过对要签名的消息进行哈希和加盐获得的。

这个签名方案的密钥是一个陷门 对于P，签名者可以用它来推导MQ方程的解。陷门向签名者揭示每个二次方程变量的隐藏分区，将变量分为“油”和“醋”变量。油变量从不相互乘，所以固定醋值会使方程变成线性系统，签名者可以解出油值。在公钥中，油和醋变量以混合的方式组合在一起，从而在映射中隐藏这种结构。

UOV也是NIST正在进行的签名标准化工作中的一个候选者。它在候选者中拥有最小的签名之一，只有135字节。权衡之处在于它拥有最大的公钥，达到46.6KB。MAYO 是另一个多元变量候选者，具有更小的公钥，代价是签名略大。

这里的关键是要记住，评估UOV（或MAYO）签名的算术复杂度与评估MQ实例相当。两者都是小二元域上的公制二次映射，非常适合VOLEitH。这带我们来到了突破。

来自VOLE-in-the-Head和UOV的盲签名

今年早些时候，一种称为PoMFRIT的盲签名被发布（Baum等人，USENIX Security 2026），它在当时实现了候选后量子构造的记录：盲签名本身为6.7KB，签发只需几百字节。PoMFRIT基于VOLE-in-the-Head和MAYO多元签名。通过用UOV替换MAYO，我们可以轻松地将签名大小降低到4.3KB。（此图使用UOV（uov-Ip）和FAEST-EM-128s的NIST第三轮参数。）权衡之处在于更大的公钥，但在公钥可以被缓存并足够频繁使用的应用中，这值得付出。

这与最先进的基于格的构造具有竞争力。但真正的好消息是，PoMFRIT的构建模块可以轻松地重新配置为我们为MOLE考虑的所有凭证系统，包括背书。更多内容稍后：目前，让我们更详细地了解一下PoMFRIT的工作原理。

设计盲签名的一种众所周知的范例 如下。首先，客户端将消息放在加密等效的密封信封中，称为承诺。对于我们而言，承诺仅仅是消息的哈希加上客户端生成的随机性。为了完成发行，签名者只需直接对承诺进行签名。

为了构造盲签名，客户端生成一个关于签名和用于计算承诺的随机数的零知识证明，称为打开。验证者将使用签名者的公钥来验证此证明。

让我们定义一些符号来使这一点更清楚：

1. 客户端生成打开 r 并将承诺c=H(m,r) 发送到其消息m 给发行人。
2. 发行人生成签名s=Sign(sk,c) 并将其发送给客户端。它不会学到消息，因为消息被哈希隐藏了。
3. 最后，客户端生成一个证明π 关于s,r ，对于它Verify(pk,H(m,r))=1,

证明 π 是盲签名。任何拥有发行者公钥 pk 和消息 m 的方都可以验证它。

不可链接性源于客户端在两个阶段呈现完全不同的对象：在发行时向发行者展示一个承诺，在展示时向验证者展示一个零知识证明。即使发行者和验证者串通一气或为同一实体，他们也无法将会话链接起来。

证明 π 的大小由哈希评估决定，因此我们需要选择一个对我们的证明系统友好的哈希函数。对于大多数证明系统，这种证明友好的哈希函数研究得还不够深入，但对于 VOLEitH，事实证明 SHAKE 和 TurboSHAKE 中使用的 Keccak 排列是一个不错的选择。Keccak 的位运算原生地转换为 VOLEitH 约束：XOR 变成加法，AND 变成乘法，旋转只是重新排列值。(相比之下，许多流行的 SNARK 是为大型素数域设计的，使得面向字节和位的操作不太自然地表达。)

然而，Keccak 评估最终成为 VOLEitH 证明中最大的组成部分，因此我们需要确保我们只使用必要数量的最少排列数。PoMFRIT 需要两个：一个用于承诺，另一个用于签名。具体来说，我们证明的陈述大致为 P(s)=H(H(m,r),r_s)，其中 s 是签名，r_s 是发行者选择的盐，P 是发行者的 UOV 公钥，H 表示输出截断到适当长度的 Keccak 排列，这也防止任何人反转。

从盲签名到背书和更远

回想一下，对于 MOLE 背书，我们需要类似盲签名的东西，但不会泄露为其签发的锚。也就是说，我们现在有一系列锚密钥 P₁，…,P_N，我们现在想要证明的陈述是 P_i(s)=H(H(m,r),r_s)，其中 P_i 是某个锚密钥，其索引 i 现在是隐藏证人的部分。

经过一些小心，我们可以将其写为一系列具有大致相同成本的约束：两个哈希和一个 MQ 评估。我们需要证明关于证人的更多内容。具体是什么？我们不会提前剧透：ZK 电路设计是使它变得如此有趣的密码工程的一部分技艺。我们只是说这里需要的思维方式几乎可以应用于你遇到的任何现代证明系统。

在这个框架中，可以构建更高级的凭证系统，包括上述匿名信用代币和匿名速率限制凭证。在这两种情况下，主要成本是额外的哈希或两个。这些每种都需要证明证人的部分（例如，信用计数）在某个预期范围内，但在 VOLEitH 中这是低成本。

确实，对于到目前为止我们为 MOLE 考虑的每种构建，主要成本是 Keccak 评估的大小以及我们需要评估它的次数。这意味着减少哈希量的方法可以在各个方面带来改进。

优化

在我们继续之前，我们需要承认多元密码学的密码分析仍然相对不成熟。在过去的几年里，我们已经看到 在几个参数体系方面取得了进展 ，UOV 和 MAYO 都很好地抵御了这些攻击，并且随着每一年的过去，UOV 和甚至 MAYO 的完全破解似乎变得更加不可能。但我们至少应该期望参数会以某种方式改变，从而增加我们构造的成本。

另一方面，在实际中使用的凭证系统为了性能而采用一种不太保守的安全态势，这是很常见的，只要它影响伪造抵抗。这通常意味着依赖于比平时更强的计算假设。也就是说，有可能出现一种（量子之前的）攻击，它可能会破解匿名信用代币，但不会破解 ECDSA，尽管它们都使用相同的椭圆曲线。

使用更少的哈希

PoMFRIT 通过做同样的事情实现了其尺寸记录。回想一下，盲签名需要证明两个哈希评估，一个由客户端执行，另一个由发行方执行。PoMFRIT 观察到 VOLEitH 证明生成可以分成两个阶段。在第一阶段，客户端向一个随机掩码承诺。然后它正常地散列消息（在 ZK 电路之外），将结果与掩码组合，并将掩码目标发送给发行方。发行方使用 UOV 陷门找到这个目标的预像。在第二阶段，客户端完成证明，该预像和先前提交的掩码是一致的。哈希仍然是协议的一部分，但发行方——作为 VOLEitH 验证器——可以直接计算它，而不是要求零知识证明来重现它。

这种策略大大减少了证明的大小，但它也改变了我们的安全态势。UOV 的基本假设是，没有（量子）攻击者可以在不知道陷门的情况下找到一个随机目标的预像。相应的“一个更多 UOV”假设（类似于 PoMFRIT 论文 中的“一个更多 MAYO”假设）准确地捕捉了攻击者由于这种优化而获得的其他信息。因此，假设是这些附加信息不会导致攻击。

这种假设可能过于乐观。最近，加州大学圣地亚哥分校和 INRIA 的研究人员设法使用 Privacy Pass 发行方作为签名预言机 伪造了一个 1024 位 RSA 签名 。幸运的是，Privacy Pass 使用 2048 位 RSA，在与其他防御机制协同工作时，提供了相当好的安全裕度。同样，对于 UOV，我们可以考虑使用 NIST 第 3 级参数而不是第 1 级参数。

在任何情况下，在过于依赖这类优化之前，我们需要进行更多研究。值得强调的是，这里的突破只会影响攻击者伪造代币的能力，而不会影响攻击者侵犯客户端隐私的能力。

使每个哈希更便宜

标准 SHAKE 使用一个 1600 位的 Keccak 状态，并应用了底层轮函数 24 次。然而，自从 SHA-3 标准发布以来，许多人开始认为 24 轮只是 太多加密。TurboSHAKE 工作方式相同，只是置换使用 12 轮而不是 24 轮。这大大减少了 VOLEitH 证明的大小。事实上，我们对这种安全裕度相当满意，不仅仅是为了这个应用。

减少 Keccak 状态大小的另一个改变是减少证明的大小。状态中有 256 位被保留用于 容量 以获得 128 位的安全性。这留下了 1344 位可以一次性散列，这比我们需要的多。将状态减半到 800 位，我们得到了 544 位的速率，这绰绰有余。除此之外，它甚至在不增加轮数的情况下提高了安全性，因为攻击者可玩的操作更少了。较小的状态意味着我们在电路中使用了半数乘法，从而减小了证明的大小。

倾向于多元式

在理想的世界里，我们可以通过用与我们的原语代数结构更自然地组合的东西来替换每个散列，从而完全避免证明传统散列。确实，那些熟悉 Pedersen 承诺 及其在椭圆曲线密码学中的应用的人可能会想知道承诺是否可以由多元式密码学构建。

这看起来有点像 这样：固定公共的随机 MQ 映射 F 和 G，并使用 c=(m+F(r),G(r)) 对消息 m 进行承诺。这种方法的优点是约束的次数与 UOV 签名的约束次数相同。这不仅使证明更小，而且使它远 simpler，因为我们避免了在 ZK 中评估对称密码。

我们针对我们的应用实验了这种方法，并得到了一些令人印象深刻的结果。然而，目前尚不清楚多元式承诺在产生改进的参数范围内是否也是安全的。值得注意的是，这里的风险不仅在于不可伪造性，还在于客户端隐私。需要更多的研究。

另一个方向是构建一个对 MQ 友好的伪随机生成器 (PRG)。

对于典型的 VOLEitH 参数，添加一个额外的证人位会给证明增加十位。有一个巧妙的方法使这变得便宜得多：每个证人位一个证明位！我们不是直接使用 VOLEitH，而是对（相对）短密钥进行承诺。我们将这个密钥扩展成一个较大的位流，使用一个低次数的 PRG，以便它可以在电路中廉价地计算。现在，要添加一个证人位 w，我们从 PRG 中获取一个额外的位 k，并将位 w XOR k 存储在证明中。

存在性能权衡：我们需要计算 PRG，并且证人从 1 次方开始变为 2 次方。这尤其增加了证明者时间。此外，证明大小上的好处只有在需要相当数量的证人位时才开始显现。

当然，你需要一个 PRG！你可以使用一个随机的 MQ 实例来创建一个 PRG，但这非常慢，似乎过于保守。另一方面是 Goldreich PRG，它可以被视为尽可能稀疏的 MQ PRG。我们 想要 介于两者之间，但这类 PRG 还没有得到太多研究。

MOLE 是否准备好迎接后量子时代？

我们如今已经拥有后量子隐私，因此我们还有一段时间不需要部署解决方案，但现在正是开发替代方案的时候。

多元密码学看起来是构建各种匿名代币和凭证的一个有前景的基础。我们目前在这个框架下正在开发两种方案：VOLE-IHAT，MOLE认定的候选方案，以及 VOLE-ACT，MOLE凭证的候选方案。这些方案的成本估算目前如下表所示。随着我们对这些构造的分析和开发，这些数字可能会发生变化。每种情况我们都使用 UOV (uov-Ip)，这意味着所有公钥都是 46.6KB。VOLEitH 使用与 FAEST-EM-128s 相同的参数：

这些数字明显大于它们的经典对应物。这并不令人意外，因为“PQ 很大”实际上是全面过渡的主要标志。然而，用 PoMFRIT 替换 RSA 盲签名与用 ML-DSA 替换 ECDSA 的开销相当。这些协议的运行时间也非常出色：我们的 实现 每次操作只需几毫秒。(运行时间可以大幅提高，但代价是更高的通信量。

如果这些数字成立，那么我们已经达到了一个重要的里程碑：现在，向 Web 过渡后量子匿名凭证可以从密码学设计转向协议工程。换句话说，我们认为这些数字是可以起作用的。例如，经典的盲签名可能足够便宜，可以在每次请求时赎回，但我们必须想办法将单次赎回分摊到多次请求上。

在到达那里之前，我们还有一些工作要做。首先，我们需要确保我们的协议是安全的，特别是通过为它们产生安全证明，证明只要 UOV 是安全的，它们就是安全的。其次，我们需要等待一点时间，让 UOV 的密码分析跟上。我们鼓励密码学家花时间研究多元密码学。一旦参数稳定下来，我们相信这些方案将在大量有用应用中找到自己的位置。到目前为止，我们才刚刚触及表面。