기술 요약: 유한 트랜스크립트를 통한 조합론적 무작위성 감사

문제 정의

로또, 랜덤니스 비콘(randomness beacon), 의사 난수 생성기(pseudorandom generators)와 같은 공공 무작위성 서비스는 조합적 추출(중복 없이 $m$개 중 $k$개의 레이블 선택)의 유한한 트랜스크립트를 생성한다. 보안 목표는 이러한 트랜스크립트를 감사하여 조작이나 구현 결함을 탐지하는 것이다. 그러나 근본적인 정보 이론적 장벽이 존재한다: 트랜스크립트 공간의 크기가 $N = \binom{m}{k}$일 때, 임의의 결합 균등성(joint uniformity)을 테스트하기 위한 표본 크기는 $\Theta(\sqrt{N}/\epsilon^2)$에 비례하여 증가한다. 현실적인 로또 파라미터(예: EuroMillions 5/50 또는 6/90)의 경우, 지지 집합(support size) $N$이 매우 커서 유한한 역사적 트랜스크립트만으로는 제한 없는 적대자에 맞서 완전한 결합 균등성을 인증할 수 없다. 또한, 어떤 분포는 모든 단일 숫자 주변 확률(marginal probabilities)을 보존하면서도 쌍(pair) 확률, 연속적 중첩(serial overlaps), 또는 추출의 기하학적 구조를 크게 변화시킬 수 있으며, 이는 표준적인 주변 확률 테스트를 무력하게 만든다.

방법론

저자들은 임의의 결합 균등성 테스트에서 벗어나, **명명된 구조적 대안 군(named structured alternative families)**을 대상으로 테스트하는 데 초점을 맞춘 "생성기 불가지론적(generator-agnostic)" 감사 프레임워크를 제안한다. 이 군(families)은 핫 레이블(hot labels), 쌍 결합(pair couplings), 연속적 끈적임(serial stickiness), 클러스터 블록(clustered blocks), 밴드 반발(band repulsion)과 같은 특정 저차원 실패 모드를 모델링한다.

통계적 프레임워크

감사 배터리는 추출물을 하이퍼심플렉스(hypersimplex)에 매핑하고 정확한 조합론적 귀무 가설 기반 통계량을 평가한다:

1. 주변 카이제곱(Marginal Chi-Square): 단일 좌표 빈도를 테스트한다.
2. 쌍 최대치(Pair Maxima): 쌍 확률의 최대 편차를 평가한다.
3. 연속적 중복(Serial Overlap): 초기하 모멘트를 사용하여 연속된 추출 간의 교집합 크기를 분석한다.
4. 앵커드 박스 불일치(Anchored-Box Discrepancy): 보정된 임계값 세트에 대한 누적 분포 함수의 편차를 측정한다.
5. $H_0$/MST 기하학: 발생 벡터(incidence vectors)를 투영하고 유클리드 최소 신장 트리(MST) 에지 스펙트럼을 분석한다.

보정 및 구현

이산적인 문제의 특성을 처리하고 연속 근사를 피하기 위해, 저자들은 **정확한 귀무 몬테카를로 보정(exact-null Monte Carlo calibration)**을 구현한다.

• 정확한 귀무 생성: 동적 계획법을 사용하여 정렬된 추출에 대한 정확한 확률을 계산하며, 연속 균등 근사에 의존하지 않는 CUDA 구현을 사용한다.
• P-값 계산: 관측된 샘플과 동일한 $(m, k, n)$ 파라미터를 가진 i.i.d. 정확한 귀무 복제본으로부터 무작위 순위 p-값을 도출한다.
• 하드웨어: 실험에는 CPU 구현과 GPU 가속(NVIDIA RTX 5090 및 A100 SXM4)을 활용하여 조건당 최대 300,000개의 귀무 복제와 60,000개의 대안 복제를 수행한다.

대안 모델

연구는 통계량의 검정력을 테스트하기 위해 다섯 가지 제어된 대안 분포를 도입한다:

• Hot-marginal: 특정 부분 집합에 대한 곱셈적 샘플링 가중치.
• Pair-injection: 확률 $\rho$로 고정된 쌍을 주입.
• Block-cluster: 확률 $\rho$로 전체 숫자 블록을 반환 (단일 숫자 주변 확률 보존).
• Band-repulsion: $k$개의 균등한 밴드에서 각 밴드당 하나의 숫자를 선택 (단일 숫자 주변 확률 보존).
• Serial-stickiness: 확률 $\rho$로 이전 추출의 레이블을 복사.

주요 결과

1. 실세계 감사 (EuroMillions)

저자들은 1,956개의 EuroMillions 메인 숫자 추출 데이터(2004–2026)를 감사했다.

• 결과: 어떤 통계량도 허위 발견 조정(false-discovery adjustment)을 통과하지 못했다. 최소 Benjamini–Hochberg q-값은 0.279였다.
• 결론: EuroMillions 트레이스는 보정된 참조 범위 내에 있으며, 테스트된 구조적 편차의 증거를 보이지 않는다.

2. 주변 확률 보존 블라인드 스폿(Blind Spots)

GPU 실험을 통해 1차원 주변 확률 테스트가 특정 결합 구조에 대해 맹목적임을 입증했다:

• Block-Cluster (강도 0.04): $n=1,956$일 때, pair max-z 통계량은 0.638의 탐지력을 달성한 반면, 주변 카이제곱은 명목 크기인 0.051에 머물렀다.
• Band-Repulsion (강도 0.08): anchored-box 통계량은 0.741의 검정력을 달성한 반면, 주변 카이제곱은 0.051에 머물렀다.
• 시사점: 어떤 분포는 단일 숫자 빈도 측면에서는 완벽하게 무작위적인 것처럼 보일 수 있으나, 결합 또는 기하학적 통계량에 의해서만 탐지 가능한 유의미한 구조적 이상을 나타낼 수 있다.

3. 표본 크기 경계(Sample-Size Frontier)

본 연구는 특정 실패 모드를 탐지하는 데 필요한 표본 크기를 정량화한다:

• 강도 0.04의 block clustering의 경우, 탐지력은 $n=1,956$에서 0.638에서 $n=5,000$에서 0.999로 상승했다.
• 강도 0.04의 band repulsion의 경우, anchored-box 검정력은 $n=1,956$에서 0.186에서 $n=20,000$에서 1.000으로 증가했다.
• 이는 임의의 균등성은 테스트 불가능하지만, 감사가 올바른 구조적 군을 타겟팅한다면 특정 구조적 편차는 트랜스크립트 길이가 증가함에 따라 탐지 가능해짐을 확인시켜 준다.

4. 포맷 확장성

더 큰 포맷(6/54 및 6/90)에 대한 실험에서도 동일한 패턴이 확인되었다: 구조적 대안에 대해 주변 확률 테스트는 명목 크기 근처에 머무는 반면, 기하학적 및 쌍 통계량은 검정력을 얻는다. 6/90 block clustering($n=5,000$)의 경우, pair max-z는 검정력 1.000을 달성했다.

의의 및 주장

본 논문은 공공 조합론적 무작위성에 대한 **블랙박스 감사 가능성 경계(black-box auditability frontier)**를 확립한다고 주장한다. 주요 기여는 다음과 같다:

1. 이론적 한계: Paninski의 하한선을 인용하여, 유한한 트랜스크립트를 가진 거대한 조합 공간에서 임의의 결합 균등성을 테스트하는 것이 불가능함을 공식적으로 규명한다.
2. 건설적 대안: 임의의 편차 대신 명명된 구조적 군을 감사하는 실행 가능한 보안 모델을 제안한다. 이 접근 방식은 $\sqrt{N}$ 표본 복잡도 장벽을 피하고, 증인 간극(witness gap)과 테스트 군의 수($L$)에 의존한다.
3. 방법론적 도구: 높은 성능의 컴퓨팅을 통해 구현되어 엄격한 검정력 분석을 가능하게 하는, 정확한 조합론적 귀무 가설에 의해 보정된 생성기 불가지론적 통계량 세트를 제공한다.
4. 경험적 분리: 주변 적합도(marginal goodness-of-fit)가 구조적 결함에 대해 맹목적일 수 있음을 경험적으로 입증함으로써, 그것이 기하학적 및 쌍 통계량에 의해 탐지 가능한 결합 구조의 실패를 식별하는 데 불충분함을 보여준다.

저자들은 완전한 결합 균등성은 유한한 트랜스크립트에서 도달할 수 없지만, "구조적 증인 군(structured witness families)"을 통해 특정 저차원 실패 모드에 대한 의미 있는 보안 주장이 가능하다고 결론짓는다. 이는 감사 표본 크기가 테스트 대상이 되는 특정 편차에 충분할 경우에 한한다.