技術的概要：直接投票用紙の選択と統計的投票用紙マニフェストに基づく亜線形リスク制限監査

1. 問題提起

リスク制限監査（RLA）は、誤った選挙結果が検出される確率が事前に設定されたリスク限界（$\alpha$）を超えないことを、厳密な統計的保証を提供するように設計された選挙後の手続きである。既存の RLA は強力なセキュリティ保証を提供するが、多様な選挙アーキテクチャにおけるその効率性と適用性を制限する 2 つの決定的なボトルネックに直面している。

1. 投票用紙マニフェストのボトルネック: 従来の RLA は、「投票用紙マニフェスト」、すなわちすべての物理的投票用紙バッチのサイズを正確かつソフトウェアに依存しない形で記録したものを必要とする。概算（例えば、重量測定によるもの）は容易に得られるが、RLA は高い精度（誤差 $\delta \ll \mu$、ここで $\mu$ は選挙の差）を要求する。この精度を達成するためには、通常、マニフェストを作成するためにすべての投票用紙を手動で数える必要がある。このプロセスは投票用紙の総数に比例して線形にスケーリング（$O(N)$）し、統計的サンプリングによる効率向上を相殺し、総監査時間を支配することが多い。
2. 投票用紙比較におけるインデックス付けのボトルネック: 最もサンプリング効率の良い RLA 手法は「投票用紙比較」であり、これはランダムに選択された投票記録（CVR）をその物理的投票用紙と照合するものである。しかし、これは識別子に基づいて特定の物理的投票用紙を効率的に特定することを必要とする。有権者向け集計機を使用する現代の選挙アーキテクチャでは、有権者のプライバシーを保護するために投票用紙が意図的にランダム化されており、CVR の順序と物理的投票用紙の順序との間のリンクが破断されている。特定の投票用紙を特定するには、バッチ内を線形検索する（コストがかかる）か、再集計を行う（コストがかかる）必要があり、これにより管轄区域は「投票用紙ポリング」や「バッチ比較」のような非効率な手法に戻らざるを得なくなる。

2. 手法

著者は、これらのボトルネックに対処し、より広範な選挙構成において亜線形の監査効率を実現するための 2 つの新しい手法を提案する。

A. 投票用紙マニフェストのための統計的精度テスト

マニフェストを確立するために完全な手動カウントを要求する代わりに、著者は統計的な「ブートストラッピング」メカニズムを提案する。

• 粗いマニフェスト: 監査人は、バッチサイズを大きな係数 $\Delta$（例えば 10%）以内で正確に提供する、低労力のバルク手法（例えば、重量測定）によって得られた「粗い」マニフェストから開始する。
• 統計的検証: 監査人は、報告された（集計された）サイズに比例する確率でバッチをサンプリングするために、この粗いマニフェストを使用する。サンプリングされた各バッチについて、監査人は真のサイズを検証するために正確な手動カウントを行う。
• 認証: 統計的テストにより、投票用紙人口の大部分について、集計されたサイズが真のサイズに十分に近いかどうかが判定される。テストが合格した場合、粗いマニフェストはすべての投票用紙を数えることなく、統計的に保証された高精度のマニフェストに「アップグレード」される。これにより、マニフェスト作成のコストは $O(N)$ から $N$ の亜線形関数に削減される。

B. 直接投票用紙の選択（DBS）

順序付き識別子がなく（標準的な投票用紙比較を妨げる）投票用紙が存在する選挙アーキテクチャに対して、著者は「直接投票用紙の選択（DBS）」を提案する。

• 逆転した手順: 標準的な比較監査（CVR を選び、投票用紙を見つける）とは異なり、DBS はバッチから物理的投票用紙を均一にランダムに選び、その押印された識別子を読み取り、対応する CVR と比較する。
• 重複検出の課題: この逆転は新たなリスクをもたらす。すなわち、敵対者が、物理的投票用紙に対応しない識別子を含めるか（または識別子を重複させる）ことで CVR テーブルを操作し、検出を回避する可能性がある。
• 統計的解決策: 著者は、識別子の一意性を検証するための新しい統計的テストを導入する。投票用紙をサンプリングし、重複または欠落した識別子をチェックすることで、監査は「過剰な識別子多重度率」を制限できる。重複が十分に稀であれば、監査はそのリスク限界を維持する。
• 複雑性: DBS のサンプリング複雑性は漸近的に $O\left(\frac{\log(1/\alpha)}{\mu}\right) + O\left(\sqrt{\frac{N \log(1/\alpha)}{\mu}}\right)$ である。2 番目の項（一意性テスト）は $\sqrt{N}$ に比例してスケーリングし、「誕生日のパラドックス」に由来する。これは、これらのアーキテクチャにおいて従来の手法が要求する線形検索よりもはるかに効率的である。

3. 主要な貢献

1. 統計的マニフェスト・ブートストラッピング: 低精度の粗いマニフェストを、亜線形の労力で高精度かつ統計的に認証されたマニフェストに変換する手法。これにより、マニフェストを確立するための完全な手動カウントの必要性が排除される。
2. 直接投票用紙の選択（DBS）: ランダム化された投票用紙順序を持つ有権者向け集計機に対応するために、標準的な比較ロジックを逆転させた新しいクラスの RLA。この手法は線形検索と再集計を回避する。
3. 重複識別子テスト: 識別子の重複または欠落のリスクを検出し制限するために監査に統合された新しい統計的テスト。物理的投票用紙を直接サンプリングする場合でもリスク限界が維持されることを保証する。
4. 統合フレームワーク: これらの手法の統合により、選挙後の観測された差に基づいて手法（ポリング、比較、または DBS）を選択できる柔軟な監査戦略が可能となり、選挙前のインフラ決定を必要としない。

4. 結果

著者は、米国（カリフォルニア州、フロリダ州、ジョージア州、コネチカット州などを含む）の選挙データと各種の差のサイズに基づいたシミュレーションを用いて、これらの手法を評価した。

• マニフェスト効率:
  • カリフォルニア州の 3% の差（1600 万枚の投票用紙）において、統計的に正確なマニフェストを使用することで、完全な手動マニフェストの作成と比較して、比較監査では総監査時間が400 倍、ポリング監査では20 倍短縮された。
  • 直接投票用紙の選択（DBS）では、重複検出のために依然として $N$ に依存する（ただし $\sqrt{N}$ に削減）ため、比較/ポリングがマニフェスト作成のために $N$ に線形依存するのに対し、削減率は8 倍であった。
• サンプリング複雑性と時間:
  • 小さな差: コネチカット州の 1% の差において、DBS は最先端のポリング手法（Minerva/Providence）と比較して、必要な投票用紙サンプルサイズを**55%**削減した。
  • 連邦下院選挙区: 0.5% から 1% の差において、DBS はサンプリング複雑性においてポリングを75% 以上上回った。
  • スケーラビリティ: これらの手法により、監査時間はマニフェスト作成の固定コストに支配されるのではなく、差 $\mu$ に応じてスケーリングするようになる。例えば、ジョージア州の 2% の差の選挙では、統計的マニフェストを使用することで監査時間は 4,000 時間から 1,200 時間に減少した。

5. 意義と主張

本論文は、これらの手法が「広範な選挙構成と差にわたる RLA の複雑性を劇的に削減する」ことを主張している。

• 亜線形効率: 主な意義は、総監査努力において亜線形効率を達成することである。完全なマニフェストの必要性と完全な手動カウントの必要性を分離し、ランダム化された環境における効率的な比較監査を可能にすることで、著者は RLA が過大な時間コストなしに大規模な選挙で実用的に展開可能であると主張する。
• ソフトウェア独立性: これらの手法は、RLA の中核的な特性であるソフトウェア独立性を維持する。マニフェストの精度と識別子の一意性に関する統計的テストは、物理的投票用紙のカウントと単純なチェックに依存しており、集計ソフトウェアの内部ロジックへの信頼を必要としない。
• 実用的適用性: 著者は、これらの手法を既存の層化 RLA フレームワークに即座に組み込むことができることを強調している。管轄区域は、競合の特定の差に基づいて、最も効率的な手法（ポリング、比較、または DBS）を動的に選択でき、セキュリティ保証を犠牲にすることなくリソース配分を最適化できる。

本論文は、漸近的な記述は直観を提供するが、明示的な数値結果は、これらの手法が、マニフェスト作成による遅延またはポリングの非効率性によるサンプリングの過剰さにより、以前は不可能であった大規模人口管轄区域や狭い差の選挙において、高保証監査を実行可能にすることを示していると結論づけている。