技術要約：有限のトランスクリプトからの組合せ論的ランダム性の監査

問題定義

ロト、ランダムネス・ビーコン、擬似乱数生成器などの公開ランダムネス・サービスは、組合せ的な抽選（$m$ 個から $k$ 個のラベルを非復元抽出）の有限なトランスクリプトを生成する。セキュリティ上の目的は、これらのトランスクリプトを監査して、改ざんや実装上の欠陥を検出することである。しかし、根本的な情報理論的障壁が存在する。トランスクリプト空間のサイズが $N = \binom{m}{k}$ である場合、任意の結合一様性をテストするには、サンプルサイズが $\Theta(\sqrt{N}/\epsilon^2)$ に比例して増大する必要がある。現実的なロトのパラメータ（例：EuroMillions 5/50 や 6/90）では、支持集合のサイズ $N$ が非常に大きいため、有限の履歴トランスクリプトを用いて、無制限の敵対者に対する完全な結合一様性を証明することは不可能である。さらに、ある分布はすべての単一数値の周辺確率を維持しつつ、ペアの確率、連続的な重複、あるいは描画の幾何学的構造を著しく変化させることが可能であり、標準的な周辺統計テストでは不十分となる。

メソドロジー

著者らは、任意の結合一様性のテストから、**「命名された構造化された代替ファミリー（named structured alternative families）」**に対するテストへと焦点を移す「ジェネレーターに依存しない（generator-agnostic）」監査フレームワークを提案している。これらのファミリーは、ホットラベル、ペアの結合、連続的な粘着性、クラスター化されたブロック、およびバンド反発といった、特定の低次元の失敗モードをモデル化している。

統計的枠組み

監査バッテリーは、描画をハイパーシンプレックス（超単体）に写像し、正確な組合せ論的帰無仮説に基づく統計量を評価する：

1. 周辺カイ二乗検定 (Marginal Chi-Square): 単一座標のカウントをテストする。
2. ペア最大値 (Pair Maxima): ペアの確率における最大偏差を評価する。
3. 連続的重複 (Serial Overlap): ハイパー幾何学的モーメントを用いて、連続する描画間の交差サイズを分析する。
4. アンカード・ボックス不一致 (Anchored-Box Discrepancy): 校正された閾値の集合上で、累積分布関数の偏差を測定する。
5. $H_0$/MST 幾何学: 発生ベクトルを投影し、ユークリッド最小全域木（MST）のエッジスペクトルを分析する。

校正と実装

離散的な問題に対処し、連続近似を避けるため、著者らは**「正確な帰無仮説によるモンテカルロ校正（exact-null Monte Carlo calibration）」**を実装している。

• 正確な帰無仮説の生成: 動的計画法を用いて、連続一様近似に頼ることなく、ソートされた描画の正確な確率を計算するCUDA実装を使用する。
• P値の計算: 同一の $(m, k, n)$ パラメータを持つ i.i.d. な正確な帰無仮説の複製から、ランダム化ランク P 値を導出する。
• ハードウェア: 実験では、最大 300,000 回の帰無仮説複製と 60,000 回の代替仮説複製を実行するために、CPU 実装および GPU 加速（NVIDIA RTX 5090 および A100 SXM4）を利用する。

代替モデル

本研究では、統計量の検出力をテストするために 5 つの制御された代替分布を導入している：

• ホット・マージナル (Hot-marginal): サブセットに対する乗法的サンプリング重み。
• ペア注入 (Pair-injection): 確率 $\rho$ で注入される固定されたペア。
• ブロック・クラスター (Block-cluster): 確率 $\rho$ で返される数値のブロック全体（単一数値の周辺確率を維持）。
• バンド反発 (Band-repulsion): $k$ 個の等しいバンドから各 1 つの数値が選択される（単一数値の周辺確率を維持、確率 $\rho$）。
• 連続的スティッキーネス (Serial-stickiness): 前回の描画からラベルをコピーする（確率 $\rho$）。

主な結果

1. 実世界の監査 (EuroMillions)

著者らは、1,956 回の EuroMillions メイン番号の描画（2004年–2026年）を監査した。

• 結果: いかなる統計量も偽発見率調整を生き残らなかった。最小の Benjamini–Hochberg q 値は 0.279 であった。
• 結論: EuroMillions のトレースは校正された参照範囲内にあり、テストされた構造化された偏差の証拠は見られなかった。

2. 周辺確率を維持する盲点

GPU 実験により、一次元の周辺テストが特定の結合構造に対して盲目であることが示された：

• ブロック・クラスター (強度 0.04): $n=1,956$ において、ペア max-z 統計量は 0.638 の検出力を達成したが、周辺カイ二乗検定は公称サイズである 0.051 のままに留まった。
• バンド反発 (強度 0.08): アンカード・ボックス統計量は 0.741 の検出力を達成したが、周辺カイ二乗検定は 0.051 のままに留まった。
• 示唆: ある分布は、単一数値の頻度に関しては完全にランダムに見える一方で、結合または幾何学的統計によってのみ検出可能な、重大な構造的異常を示す可能性がある。

3. サンプルサイズの境界

本研究は、特定の失敗モードを検出するために必要なサンプルサイズを定量化している：

• 強度 0.04 のブロック・クラスターについて、検出力は $n=1,956$ で 0.638 から $n=5,000$ で 0.999 へと上昇した。
• 強度 0.04 のバンド反発について、アンカード・ボックスの検出力は $n=1,956$ で 0.186 から $n=20,000$ で 1.000 へと上昇した。
• これは、任意の一様性はテスト不可能であるが、監査が正しい構造的ファミリーを対象としている限り、特定の構造化された偏差はトランスクリプトの長さが増すにつれて検出可能になることを裏付けている。

4. フォーマットの拡張性

より大きなフォーマット（6/54 および 6/90）を用いた実験により、このパターンが維持されることが確認された。周辺テストは構造化された代替モデルに対して公称サイズのまま推移する一方、幾何学的およびペア統計は検出力を獲得する。6/90 のブロック・クラスターにおいて、$n=5,000$ のときペア max-z は検出力 1.000 を達成した。

意義と主張

本論文は、公開された組合せ論的ランダムネスに対する**「ブラックボックス監査の境界」**を確立したと主張している。その主な貢献は以下の通りである：

1. 理論的限界: 有限のトランスクリプトを用いた大規模な組合せ空間における、任意の結合一様性をテストすることの不可能性を、Paninski の下界を引用して形式的に特徴づけた。
2. 建設的な代替案: 任意の偏差ではなく、**「命名された構造化されたファミリー」**を監査するという実行可能なセキュリティモデルを提案した。このアプローチは、$\sqrt{N}$ のサンプル複雑性の壁を、証拠のギャップとテスト・ファミリーの数 ($L$) に依存させることで回避する。
3. メソドロジー・ツール: 高性能コンピューティングを用いて校正された、ジェネレーターに依存しない一連の統計量を提供し、厳密なパワー分析を可能にした。
4. 経験的な分離: 周辺の適合度検定は、幾何学的およびペア統計によって検出可能な結合構造の失敗に対して、正確に盲目になり得ることを経験的に示した。

著者らは、有限のトランスクリプトでは完全な結合一様性は到達不能であるが、「構造化された証拠ファミリー（structured witness families）」を用いることで、特定の低次元の失敗モードに関する有意義なセキュリティ主張が可能になると結論付けている。