Résumé Technique : Audit de l'Aléatoire Combinatoire à partir de Transcrits Finis

Énoncé du Problème

Les services de hasard public, tels que les loteries, les balises d'aléatoire (randomness beacons) et les générateurs de nombres pseudo-aléatoires, produisent des transcrits finis de tirages combinatoires (sélection de $k$ étiquettes parmi $m$ sans remise). L'objectif de sécurité est d'auditer ces transcrits pour détecter toute manipulation ou toute défaillance d'implémentation. Cependant, une barrière fondamentale d'ordre informationnel existe : pour un espace de transcrits de taille $N = \binom{m}{k}$, le test d'une uniformité jointe arbitraire nécessite une taille d'échantillon proportionnelle à $\Theta(\sqrt{N}/\epsilon^2)$. Pour des paramètres de loterie réalistes (par exemple, EuroMillions 5/50 ou 6/90), la taille du support $N$ est si grande que les transcrits historiques finis ne peuvent certifier une pleine uniformité jointe contre un adversaire non restreint. De plus, une distribution peut préserver toutes les probabilités marginales de nombres isolés tout en modifiant significativement les probabilités de paires, les chevauchements sériels ou la structure géométrique des tirages, rendant les tests marginaux standards inefficaces.

Méthodologie

Les auteurs proposent un cadre d'audit « agnostique au générateur » qui déplace l'attention de l'uniformité jointe arbitraire vers le test de familles d'alternatives structurées nommées. Ces familles modélisent des modes de défaillance spécifiques et de faible dimension tels que les étiquettes « chaudes » (hot labels), les couplages de paires, l'adhérence sérielle, les blocs groupés et la répulsion de bandes.

Cadre Statistique

La batterie d'audits projette les tirages sur l'hypersimplex et évalue des statistiques exactes à calibration combinatoire nulle :

1. Chi-Carré Marginal : Teste les comptes de coordonnées uniques.
2. Maxima de Paires : Évalue l'écart maximal dans les probabilités de paires.
3. Chevauchement Sériel : Analyse la taille de l'intersection entre des tirages consécutifs en utilisant des moments hypergéométriques.
4. Écart de Boîte Ancrée (Anchored-Box Discrepancy) : Mesure l'écart des fonctions de répartition cumulative sur un ensemble de seuils calibrés.
5. Géométrie $H_0$/MST : Projette les vecteurs d'incidence et analyse le spectre des arêtes de l'arbre couvrant minimal euclidien (MST).

Calibration et Implémentation

Pour gérer la nature discrète du problème et éviter les approximations continues, les auteurs implémentent une calibration par Monte Carlo de la nullité exacte.

• Génération de la Nullité Exacte : Une implémentation CUDA utilise la programmation dynamique pour calculer les probabilités exactes pour les tirages triés, sans dépendre d'approximations uniformes continues.
• Calcul des P-values : Des p-values de rang aléatoire sont dérivées de réplications de la nullité exacte i.i.d. générées avec les mêmes paramètres $(m, k, n)$ que l'échantillon observé.
• Matériel : Les expériences utilisent des implémentations CPU et l'accélération GPU (NVIDIA RTX 5090 et A100 SXM4) pour effectuer jusqu'à 300 000 réplications de la nullité et 60 000 réplications alternatives par condition.

Modèles Alternatifs

L'étude introduit cinq distributions alternatives contrôlées pour tester la puissance des statistiques :

• Hot-marginal : Poids d'échantillonnage multiplicatifs sur un sous-ensemble.
• Injection de Paires : Paires fixes injectées avec une probabilité $\rho$.
• Bloc-Cluster : Blocs entiers de nombres retournés avec une probabilité $\rho$ (préservant les marginales de nombres isolés).
• Répulsion de Bande (Band-repulsion) : Un nombre sélectionné dans chacune des $k$ bandes égales avec une probabilité $\rho$ (préservant les marginales de nombres isolés).
• Adhérence Sérielle (Serial-stickiness) : Copie d'une étiquette du tirage précédent avec une probabilité $\rho$.

Résultats Clés

1. Audit Réel (EuroMillions)

Les auteurs ont audité 1 956 tirages principaux d'EuroMillions (2004–2026).

• Résultat : Aucune statistique n'a survécu à l'ajustement de la découverte de fausses alarmes (false-discovery adjustment). La valeur q de Benjamini–Hochberg minimale était de 0,279.
• Conclusion : La trace de l'EuroMillions se situe dans la plage de référence calibrée, ne montrant aucune preuve des déviations structurées testées.

2. Angles Morts Préservant les Marginales

Les expériences sur GPU ont démontré que les tests marginaux unidimensionnels sont aveugles à certaines structures conjointes :

• Bloc-Cluster (Force 0,04) : Pour $n=1 956$, la statistique pair max-z a atteint une puissance de détection de 0,638, tandis que le chi-carré marginal est resté à sa taille nominale de 0,051.
• Répulsion de Bande (Force 0,08) : La statistique anchored-box a atteint une puissance de 0,741, tandis que le chi-carré marginal est resté à 0,051.
• Implication : Une distribution peut paraître parfaitement aléatoire en termes de fréquence de nombres isolés tout en présentant des anomalies structurelles significatives détectables uniquement par des statistiques conjointes ou géométriques.

3. Frontière de la Taille d'Échantillon

L'étude quantifie les tailles d'échantillon requises pour détecter des modes de défaillance spécifiques :

• Pour le bloc groupé (block clustering) à une force de 0,04, la puissance de détection est passée de 0,638 à $n=1 956$ à 0,999 à $n=5 000$.
• Pour la répulsion de bande à une force de 0,04, la puissance de l'anchored-box est passée de 0,186 à $n=1 956$ à 1,000 à $n=20 000$.
• Cela confirme que, bien que l'uniformité arbitraire soit invérifiable, les déviations structurées spécifiques deviennent détectables à mesure que la longueur du transcrit augmente, à condition que l'audit cible la bonne famille structurelle.

4. Scalabilité du Format

Des expériences sur des formats plus larges (6/54 et 6/90) ont confirmé que le schéma se maintient : les tests marginaux restent proches de la taille nominale pour les alternatives structurées, tandis que les statistiques géométriques et de paires gagnent en puissance. Pour le bloc groupé de 6/90 à $n=5 000$, le pair max-z a atteint une puissance de 1,000.

Signification et Revendications

L'article prétend établir une frontière d'auditabilité en boîte noire pour l'aléatoire combinatoire public. Ses principales contributions sont :

1. Limite Théorique : Il caractérise formellement l'impossibilité de tester l'uniformité jointe arbitraire pour de grands espaces combinatoires avec des transcrits finis, citant les bornes inférieures de Paninski.
2. Alternative Constructive : Il propose un modèle de sécurité viable basé sur l'audit de familles structurées nommées plutôt que sur des déviations arbitraires. Cette approche évite la barrière de complexité d'échantillonnage en $\sqrt{N}$ en dépendant de l'écart du témoin (witness gap) et du nombre de familles de tests ($L$).
3. Outillage Méthodologique : Il fournit une suite de statistiques agnostiques au générateur, calibrées contre la nullité combinatoire exacte, implémentées avec du calcul haute performance pour permettre une analyse de puissance rigoureuse.
4. Séparation Empirique : Il démontre empiriquement que la qualité d'ajustement marginal est insuffisante pour l'audit de sécurité, car elle peut être exactement aveugle aux défaillances de structure conjointe qui sont pourtant détectables par les statistiques géométriques et de paires.

Les auteurs concluent que, bien que l'uniformité jointe totale soit hors de portée pour des transcrits finis, les « familles de témoins structurées » permettent de formuler des affirmations de sécurité significatives concernant des modes de défaillance de faible dimension, à condition que la taille de l'échantillon d'audit soit suffisante pour la déviation spécifique testée.