기술적 요약: 직접 투표지 선정과 통계적 투표지 매니페스트를 통한 아선형 위험 제한 감사

1. 문제 제기

위험 제한 감사 (RLA) 는 부정확한 선거 결과가 사전에 지정된 위험 한도 ($\alpha$) 를 초과할 확률로 탐지되지 않도록 엄격한 통계적 보장을 제공하는 선거 후 절차입니다. 기존 RLA 는 강력한 보안 보장을 제공하지만, 다양한 선거 아키텍처 전반에서 효율성과 적용 가능성을 제한하는 두 가지 주요 병목 현상에 직면해 있습니다:

1. 투표지 매니페스트 병목 현상: 기존 RLA 는 모든 물리적 투표지 배치의 크기에 대한 정확하고 소프트웨어 독립적인 계정인 "투표지 매니페스트"를 요구합니다. 대략적인 추정 (예: 무게 측정) 은 쉽게 얻을 수 있지만, RLA 는 높은 정확도 (오차 $\delta \ll \mu$, 여기서 $\mu$는 선거 마진) 를 요구합니다. 이러한 정확도를 달성하려면 일반적으로 매니페스트를 작성하기 위해 모든 투표지를 수동으로 일일이 세야 합니다. 이 과정은 총 투표지 수 ($O(N)$) 에 비례하여 선형적으로 확장되며, 종종 감사 총 시간을 지배하여 통계적 샘플링의 효율성 향상을 무효화합니다.
2. 투표지 비교에서의 인덱싱 병목 현상: 가장 샘플 효율적인 RLA 방법은 무작위로 선정된 기표된 투표 기록 (CVR) 을 해당 물리적 투표지와 매칭하는 "투표지 비교"입니다. 그러나 이는 식별자를 기반으로 특정 물리적 투표지를 효율적으로 찾아야 합니다. 유권자용 집계기를 사용하는 현대 선거 아키텍처에서는 유권자 프라이버시를 보호하기 위해 투표지를 의도적으로 무작위화하여 CVR 의 순서와 물리적 투표지 순서 간의 연결을 끊습니다. 특정 투표지를 찾으려면 배치 내에서 선형 검색 (비효율적) 이나 재집계 (비효율적) 가 필요하므로, 관할 구역은 "투표지 풀링"이나 "배치 비교"와 같이 덜 효율적인 방법으로 되돌아가야 합니다.

2. 방법론

저자들은 이러한 병목 현상을 해결하고 더 넓은 범위의 선거 구성에서 아선형 감사 효율성을 가능하게 하는 두 가지 새로운 기법을 제안합니다.

A. 투표지 매니페스트를 위한 통계적 정확도 테스트

매니페스트를 수립하기 위해 전체 수동 계산을 요구하는 대신, 저자들은 통계적 "부트스트래핑" 메커니즘을 제안합니다.

• 대략적 매니페스트: 감사자는 배치 크기를 큰 계수 $\Delta$(예: 10%) 이내로 정확하게 제공하는 저효율 대량 방법 (예: 무게 측정) 을 통해 얻은 "대략적" 매니페스트로 시작합니다.
• 통계적 검증: 감사자는 보고된 (집계된) 크기에 비례하는 확률로 배치를 샘플링하기 위해 대략적 매니페스트를 사용합니다. 각 샘플링된 배치에 대해 감사자는 실제 크기를 확인하기 위해 정밀한 수동 계산을 수행합니다.
• 인증: 통계적 테스트는 투표지 대다수에 대해 집계된 크기가 실제 크기에 충분히 근접한지 여부를 결정합니다. 테스트가 통과하면, 모든 투표지를 세지 않고도 대략적 매니페스트가 통계적으로 보장된 고정밀 매니페스트로 "업그레이드"됩니다. 이를 통해 매니페스트 작성 비용이 $O(N)$에서 $N$의 아선형 함수로 감소합니다.

B. 직접 투표지 선정 (DBS)

투표지에 순차적 식별자가 없어 (표준 투표지 비교를 방해) 유권자용 집계기를 사용하는 선거 아키텍처의 경우, 저자들은 "직접 투표지 선정 (Direct Ballot Selection)"을 제안합니다.

• 역방향 절차: 표준 비교 감사 (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. 주요 기여

1. 통계적 매니페스트 부트스트래핑: 저정확도 대략적 매니페스트를 아선형 노력으로 고정밀 통계 인증 매니페스트로 변환하는 방법입니다. 이는 매니페스트 수립을 위한 포괄적인 수동 계산의 필요성을 제거합니다.
2. 직접 투표지 선정 (DBS): 무작위화된 투표지 순서를 가진 유권자용 집계기를 수용하기 위해 표준 비교 논리를 역전시키는 RLA 의 새로운 클래스입니다. 이 방법은 선형 검색과 재집계를 피합니다.
3. 중복 식별자 테스트: 감사에 통합된 새로운 통계적 테스트로, 식별자 중복 또는 누락의 위험을 탐지하고 제한하여 물리적 투표지를 직접 샘플링할 때에도 위험 한도가 유효하도록 보장합니다.
4. 통합 프레임워크: 이러한 기법들의 통합은 선거 후 관측된 마진에 따라 방법 (풀링, 비교, 또는 DBS) 을 선택할 수 있는 유연한 감사 전략을 가능하게 하며, 선거 전 인프라 결정을 요구하지 않습니다.

4. 결과

저자들은 미국 선거 데이터 (캘리포니아, 플로리다, 조지아, 코네티컷 등 주 포함) 와 다양한 마진 크기를 기반으로 한 시뮬레이션을 사용하여 기법을 평가했습니다.

• 매니페스트 효율성:
  • 캘리포니아의 3% 마진 (1,600 만 장의 투표지) 의 경우, 통계적으로 정확한 매니페스트를 사용하면 전체 매니페스트를 수동으로 작성하는 것에 비해 비교 감사의 총 감사 시간을 400 배, 풀링 감사의 경우 20 배 단축했습니다.
  • 직접 투표지 선정의 경우, 고유성 테스트를 위해 여전히 $N$에 의존하지만 ($\sqrt{N}$으로 감소됨) 비교/풀링이 매니페스트 작성에 대해 $N$에 선형적으로 의존하는 반면, 감소 폭은 8 배였습니다.
• 샘플 복잡도 및 시간:
  • 소규모 마진: 코네티컷의 1% 마진의 경우, 직접 투표지 선정은 최첨단 풀링 방법 (Minerva/Providence) 에 비해 필요한 투표지 샘플 크기를 55% 감소시켰습니다.
  • 연방 하원 선거구: 0.5% 에서 1% 사이의 마진의 경우, DBS 는 샘플 복잡도 측면에서 풀링보다 75% 이상 개선되었습니다.
  • 확장성: 이러한 기법들은 감사 시간이 매니페스트 작성의 고정 비용에 의해 지배되는 것이 아니라 마진 $\mu$에 따라 확장되도록 합니다. 예를 들어, 조지아의 2% 마진 경쟁에서 통계적 매니페스트를 사용하면 감사 시간이 4,000 시간에서 1,200 시간으로 감소했습니다.

5. 중요성 및 주장

이 논문은 이러한 기법들이 "다양한 선거 구성과 마진 전반에 걸쳐 RLA 의 복잡성을 획기적으로 감소시킨다"고 주장합니다.

• 아선형 효율성: 주요 중요성은 총 감사 노력에서 아선형 효율성을 달성하는 데 있습니다. 완벽한 매니페스트 필요성과 전체 수동 계산 필요성을 분리하고, 무작위화된 환경에서 효율적인 비교 감사를 가능하게 함으로써, 저자들은 RLA 가 prohibitive 한 시간 비용 없이 대규모 선거에서 실제로 배포될 수 있다고 주장합니다.
• 소프트웨어 독립성: 이 방법들은 RLA 의 핵심 속성인 소프트웨어 독립성을 유지합니다. 매니페스트 정확도와 식별자 고유성에 대한 통계적 테스트는 물리적 투표지 계산과 간단한 검사를 기반으로 하며, 집계 소프트웨어의 내부 논리에 대한 신뢰를 요구하지 않습니다.
• 실용적 적용 가능성: 저자들은 이러한 방법이 기존 계층화 RLA 프레임워크에 즉시 통합될 수 있음을 강조합니다. 관할 구역은 경쟁의 특정 마진에 따라 가장 효율적인 방법 (풀링, 비교, 또는 DBS) 을 동적으로 선택하여 보안 보장을 희생하지 않고 자원 할당을 최적화할 수 있습니다.

이 논문은 점근적 진술은 직관을 제공하지만, 명시적인 수치적 결과는 이러한 기법이 이전 방법들이 매니페스트 작성으로 인해 너무 느리거나 (풀링 비효율성으로 인해) 샘플이 너무 많이 필요한 대규모 인구 관할 구역과 좁은 마진에서 고보장 감사를 실현 가능하게 만든다고 결론지었습니다.