💻 computer science

Sublinear Risk-Limiting Audits from Direct Ballot Selection and Statistical Ballot Manifests

本文介绍了两种新颖的风险限制审计技术——一种以次线性工作量验证选票清单的统计方法，以及一种直接选票选择方法——它们显著降低了选举审计（尤其是得票率差距较小的选举）所需的时间和样本复杂度。

原作者： Benjamin Fuller, Abigail Harrison, Alexander Russell

发布于 2026-05-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Benjamin Fuller, Abigail Harrison, Alexander Russell

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一场选举就像一座庞大而混乱的图书馆，数百万人刚刚借出了书籍（即投出了选票）。图书馆的计算机系统（即计票器）打印出一份清单，说明谁借了哪本书。但我们如何知道计算机没有出错，或者更糟，没有遭到黑客攻击呢？

这就是**风险限制审计（RLAs）**发挥作用的地方。将 RLA 视为一种“抽查”，它能以高度的统计置信度保证选举获胜者是正确的。如果计算机在撒谎，这种抽查几乎肯定能将其揪出。

然而，进行这些抽查存在两个巨大且昂贵的问题，而本文解决了这些问题：

“库存清单”问题：要检查书籍，你需要一份完美的清单，列出每个箱子（批次）中有多少本书。要完美地制作这份清单，通常意味着要手工清点每一本书，这违背了快速抽查的初衷。
“洗乱的牌堆”问题：在许多现代投票机中，纸质选票的物理顺序被故意打乱，以保护选民隐私。这使得根据计算机清单上的“第 4,502 号书”在书架上找到特定的一本书变得极其困难。

作者提出了两种新的“魔法技巧”，无需清点每一张选票即可解决这些问题。

1. “称重秤”技巧（统计清单）

问题：传统上，要信任库存清单（即“manifest"），你必须清点每个箱子里的每一张选票。如果清单显示一个箱子里有 100 张选票，你就必须清点 100 张才能确认。即使偏差再微小，整个审计也可能被推翻。

解决方案：作者建议先使用“粗略估计”，就像称一箱书的重量一样。你知道 100 本书的箱子大约重 10 磅。你不需要清点它们就能知道它大约有 100 本。

比喻：想象你有 1,000 箱书。与其打开每个箱子去清点，不如把它们全部称重。你会得到一份“粗略”的清单，其准确度为 90%。
魔法：作者创建了一种统计测试，利用这份“粗略”清单来验证计算机的“完美”清单。他们随机挑选几个箱子，称重，然后实际清点这几个箱子里的书。如果清点结果与计算机的声明在极小的误差范围内相符，该测试就能将粗略估计“提升”（bootstrap）为一份受信任的高精度清单。
结果：你不必清点每一张选票就能获得受信任的清单。你只需清点一小部分。对于像加利福尼亚州这样的大州，这将准备审计清单的时间缩短了400 倍。

2. “反向搜索”技巧（直接选票选择）

问题：通常，审计是这样进行的：计算机说：“检查 ID 为#999 的选票。”审计员随后必须在成千上万张打乱的选票堆中费力寻找 ID 为#999 的那张。这种“搜索”既缓慢又昂贵。

解决方案：作者扭转了局面。他们不是根据计算机 ID 寻找特定选票，而是直接从箱子里随机抓取一张物理选票，读取其 ID，然后询问计算机：“你说这张选票投给了谁？”

比喻：与其在干草堆里寻找特定的针，不如直接抓一把干草，看看你找到的针，并检查它们是否与清单匹配。
隐患：如果计算机在撒谎，其清单上包含现实中任何选票都不存在的“假”ID（重复号码），这种方法可能会被欺骗。
修复：作者增加了一项第二项统计测试来检查“假针”。他们计算在随机抓取中看到相同 ID 两次的频率。如果重复出现的情况很罕见（理应如此），审计就是安全的。
结果：这种方法对于小幅度选举（势均力敌的选举）要快得多。在康涅狄格州的一场势均力敌的选举中，这种方法比当前最佳方法快了55%，因为它完全跳过了缓慢的“搜索”步骤。

大局：为何这很重要

该论文声称，通过结合这两种技巧，我们可以更快、更便宜地审计选举，即使是在拥有数百万选民的巨大州份也是如此。

速度：在加利福尼亚州，过去进行完整审计仅制作库存清单就需要数千小时。采用这些新方法后，这一时间被大幅削减。
效率：对于势均力敌的选举（获胜者仅由极小比例的选票决定），旧方法需要检查如此多的选票，以至于变得不切实际。新的“直接选票选择”方法能更好地处理这些势均力敌的选举。
灵活性：无论选票是整齐排列还是杂乱堆叠，这些方法都适用。

简而言之：作者找到了一种信任库存“粗略猜测”和选票“随机抓取”的方法，利用巧妙的数学证明这些捷径与旧式缓慢的“清点一切”方法一样安全。这使得验证选举结果对每个人来说都更快、更便宜、更切实可行。

技术摘要：基于直接选票选择与统计选票清单的次线性风险限制审计

1. 问题陈述

风险限制审计（RLAs）是选举后程序，旨在提供严格的统计保证，确保以不超过预设风险限额（ $\alpha$ ）的概率检测出错误的选举结果。尽管现有的 RLAs 提供了强有力的安全保证，但它们面临两个关键瓶颈，限制了其在多样化选举架构中的效率和适用性：

选票清单瓶颈：传统的 RLAs 需要一份“选票清单”——即对每一批物理选票规模进行准确且软件独立的核算。虽然粗略估算（例如通过称重）很容易获得，但 RLAs 需要高精度（误差 $\delta \ll \mu$ ，其中 $\mu$ 为选举差距）。实现这种精度通常需要对每张选票进行人工手工计数以创建清单。该过程随选票总数呈线性扩展（ $O(N)$ ），往往主导了总审计时间，从而抵消了统计抽样的效率增益。
选票比较中的索引瓶颈：样本效率最高的 RLA 方法是“选票比较”，即将随机选出的已投票记录（CVR）与其物理选票进行匹配。然而，这需要基于标识符高效地定位特定的物理选票。在现代选举架构中，使用面向选民的计票机时，选票会被故意随机化以保护选民隐私，从而切断了 CVR 顺序与选票物理顺序之间的联系。定位特定选票随后需要对批次进行线性搜索（成本高昂）或重新计票（成本高昂），迫使司法管辖区退回到效率较低的方法，如“选票抽样”或“批次比较”。

2. 方法论

作者提出了两种新技术来解决这些瓶颈，从而在更广泛的选举配置中实现次线性的审计效率。

A. 选票清单的统计准确性测试

作者提出了一种统计“自举”机制，以替代建立清单所需的全面手工计数。

粗略清单：审计人员从通过低努力批量方法（例如称重）获得的“粗略”清单开始，该清单提供的批次规模精度在较大因子 $\Delta$ （例如 10%）之内。
统计验证：审计人员利用粗略清单，按报告（计票）规模成比例的概率对批次进行抽样。对于每个抽样的批次，审计人员进行精确的手工计数以验证真实规模。
认证：一项统计测试用于确定报告规模是否与绝大多数选票群体的真实规模足够接近。如果测试通过，粗略清单即被“升级”为具有统计保证的高精度清单，而无需清点每张选票。这将清单创建的成本从 $O(N)$ 降低为 $N$ 的次线性函数。

B. 直接选票选择（DBS）

对于缺乏顺序标识符（从而阻碍标准选票比较）的选举架构，作者提出了“直接选票选择”。

逆向程序：与标准比较审计（选取 CVR 并查找选票）不同，DBS 从批次中均匀随机地选取一张物理选票，读取其打印的标识符，并将其与相应的 CVR 进行比较。
重复检测挑战：这种逆转引入了新的风险：攻击者可能通过包含不对应任何物理选票的标识符（或重复标识符）来操纵 CVR 表，从而逃避检测。
统计解决方案：作者引入了一种新的标识符唯一性统计测试。通过抽样选票并检查重复或缺失的标识符，审计可以界定“多余标识符多重率”。如果重复足够罕见，审计就能维持其风险限制。
复杂度：DBS 的样本复杂度渐近为 $O\left(\frac{\log(1/\alpha)}{\mu}\right) + O\left(\sqrt{\frac{N \log(1/\alpha)}{\mu}}\right)$ 。第二项（唯一性测试）随 $\sqrt{N}$ 扩展，源于“生日悖论”，这比这些架构中传统方法所需的线性搜索要高效得多。

3. 主要贡献

统计清单自举：一种将低精度、粗略清单转化为高精度、统计认证清单的方法，所需努力为次线性。这消除了为建立清单而进行 exhaustive 手工计数的需求。
直接选票选择（DBS）：一类新的 RLAs，通过逆转标准比较逻辑来适应具有随机化选票顺序的面向选民计票机。该方法避免了线性搜索和重新计票。
重复标识符测试：一种集成到审计中的新颖统计测试，用于检测并界定标识符重复或遗漏的风险，确保即使在直接抽样物理选票时风险限制依然成立。
统一框架：这些技术的整合允许一种灵活的审计策略，其中方法的选择（抽样、比较或 DBS）可以在选举后根据观察到的差距做出，而不是需要在选举前做出基础设施决策。

4. 结果

作者利用基于美国选举数据（包括加利福尼亚州、佛罗里达州、佐治亚州和康涅狄格州等州）及不同差距规模的模拟评估了他们的技术。

清单效率：
- 对于加利福尼亚州 3% 的差距（1600 万张选票），使用统计准确的清单，与创建完整手工清单相比，比较审计的总审计时间减少了 400 倍，抽样审计减少了 20 倍。
- 对于直接选票选择，减少倍数为 8 倍，因为该方法仍依赖 $N$ （尽管减少为 $\sqrt{N}$ ）进行唯一性测试，而比较/抽样在清单创建上则线性依赖 $N$ 。
样本复杂度与时间：
- 小差距：对于康涅狄格州 1% 的差距，与最先进的抽样方法（Minerva/Providence）相比，直接选票选择将所需的选票样本量减少了 55%。
- 国会选区：对于 0.5% 到 1% 之间的差距，DBS 在样本复杂度上比抽样方法提高了 75% 以上。
- 可扩展性：这些技术使得审计时间随差距 $\mu$ 扩展，而不是受限于清单创建的固定成本。例如，在佐治亚州一场 2% 差距的竞选中，通过使用统计清单，审计时间从 4,000 小时降至 1,200 小时。

5. 意义与主张

该论文声称，这些技术在广泛的选举配置和差距中提供了“风险限制审计复杂性的显著降低”。

次线性效率：主要意义在于实现了总审计努力的次线性效率。通过将完美清单的需求与全面手工计数的需求解耦，并实现在随机化环境中的高效比较审计，作者认为 RLAs 可以在大规模选举中实际部署，而不会产生 prohibitive 的时间成本。
软件独立性：这些方法保持了 RLA 的核心属性——软件独立性。清单准确性和标识符唯一性的统计测试依赖于物理选票计数和简单检查，无需信任计票软件内部逻辑。
实际适用性：作者强调，这些方法可以立即纳入现有的分层 RLA 框架。司法管辖区可以根据特定竞争的差距动态选择最有效的方法（抽样、比较或 DBS），在优化资源配置的同时不牺牲安全保证。

该论文得出结论，尽管渐近陈述提供了直观理解，但明确的数值结果表明，这些技术使得高保障审计对于人口众多的司法管辖区和紧密差距变得可行，而之前的方法要么因清单创建而太慢，要么因抽样效率低下而样本量过大。