💻 computer science

Sublinear Risk-Limiting Audits from Direct Ballot Selection and Statistical Ballot Manifests

Dit artikel introduceert twee nieuwe risicogelimiteerde audittechnieken—een statistische methode voor het verifiëren van stembiljetmanifesten met sublineaire inspanning en een directe benadering voor het selecteren van stembiljetten—die de tijd en steekproefcomplexiteit die nodig zijn voor het auditen van verkiezingen, met name die met nauwe marges, aanzienlijk verminderen.

Oorspronkelijke auteurs: Benjamin Fuller, Abigail Harrison, Alexander Russell

Gepubliceerd 2026-05-19

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Benjamin Fuller, Abigail Harrison, Alexander Russell

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een verkiezing voor als een enorme, chaotische bibliotheek waar miljoenen mensen zojuist boeken hebben uitgeleend (hun stem hebben uitgebracht). Het computersysteem van de bibliotheek (de stemteller) print een lijst uit met wie welk boek heeft uitgeleend. Maar hoe weten we dat de computer geen fout heeft gemaakt, of erger, gehackt is?

Hier komen Risicolimiet-Audits (RLA's) om de hoek kijken. Denk aan een RLA als een "steekproef" die met een hoge statistische zekerheid garandeert dat de winnaar van de verkiezing correct is. Als de computer liegt, is het vrijwel gegarandeerd dat de steekproef dit opspoort.

Het uitvoeren van deze steekproeven heeft echter twee enorme, dure problemen die dit artikel oplost:

Het "Inventarislijst"-Probleem: Om de boeken te controleren, heb je een perfecte lijst nodig van hoeveel boeken er in elke afzonderlijke doos (batch) zitten. Een dergelijke lijst perfect maken betekent meestal dat je elk enkel boek handmatig moet tellen, wat de bedoeling van een snelle steekproef tenietdoet.
Het "Geschoorde Deck"-Probleem: Bij veel moderne stemmachines is de volgorde van de fysieke stembiljetten opzettelijk door elkaar gehaald om de privacy van de kiezer te beschermen. Hierdoor is het ontzettend moeilijk om een specifiek boek op het plankje te vinden, alleen omdat de computerlijst zegt "Boek #4.502".

De auteurs stellen twee nieuwe "magische trucs" voor om deze problemen op te lossen zonder dat elke stembiljet geteld hoeft te worden.

1. De "Weegschaal"-Truc (Statistische Manifesten)

Het Probleem: Traditioneel moest je, om te vertrouwen op de inventarislijst (het "manifest"), elke stembiljet in elke doos tellen. Als de lijst aangaf dat een doos 100 stembiljetten bevatte, moest je er 100 tellen om zeker te zijn. Als je zelfs maar een klein beetje afweek, kon de hele audit worden verworpen.

De Oplossing: De auteurs suggereren eerst een "ruwe schatting" te gebruiken, zoals het wegen van een doos boeken. Je weet dat een doos met 100 boeken ongeveer 4,5 kilo weegt. Je hoeft ze niet te tellen om te weten dat het er ongeveer 100 zijn.

De Metafoor: Stel je hebt 1.000 dozen boeken. In plaats van elke doos open te maken om te tellen, weeg je ze allemaal. Je krijgt een "grove" lijst die 90% accuraat is.
De Magie: De auteurs hebben een statistische test ontwikkeld die deze "grove" lijst gebruikt om de "perfecte" lijst van de computer te verifiëren. Ze kiezen willekeurig een paar dozen, wegen ze, en tellen vervolgens daadwerkelijk de boeken in slechts die paar dozen. Als de telling binnen een kleine foutmarge overeenkomt met de bewering van de computer, "bootstrapt" (tilt) de test de ruwe schatting omhoog naar een vertrouwde, hoog-accurate lijst.
Het Resultaat: Je hoeft niet elke stembiljet te tellen om een vertrouwde lijst te krijgen. Je telt slechts een klein deel. Voor een enorme staat als Californië verkort dit de tijd om de auditlijst voor te bereiden met een factor van 400.

2. De "Omgekeerde Zoek"-Truc (Directe Stembiljetselectie)

Het Probleem: Meestal werkt een audit als volgt: De computer zegt: "Controleer het stembiljet met ID #999." De auditor moet dan door een rommelige bak met duizenden door elkaar gehaalde stembiljetten jagen om degene met ID #999 te vinden. Deze "zoektocht" is traag en duur.

De Oplossing: De auteurs draaien de zaak om. In plaats van een specifiek stembiljet te zoeken op basis van een computer-ID, grijpen ze gewoon een willekeurig fysiek stembiljet uit een doos, lezen de ID en vragen de computer vervolgens: "Wat zei je dat dit stembiljet heeft uitgebracht?"

De Metafoor: In plaats van te zoeken naar een specifieke naald in een hooiberg, pak je gewoon een handvol hooi, bekijkt de naalden die je hebt gevonden en controleert of ze overeenkomen met de lijst.
De Haken: Als de computer liegt en "valse" ID's (dubbele nummers) op zijn lijst heeft staan die niet bestaan op een echt stembiljet, kan deze methode worden bedrogen.
De Oplossing: De auteurs hebben een tweede statistische test toegevoegd om te controleren op "valse naalden". Ze tellen hoe vaak ze in hun willekeurige greep hetzelfde ID twee keer zien. Als duplicaten zeldzaam zijn (zoals ze zouden moeten zijn), is de audit veilig.
Het Resultaat: Deze methode is veel sneller voor kleine verkiezingsmarges (dicht bij elkaar liggende races). Voor een nauwe race in Connecticut is deze methode 55% sneller dan de huidige beste methoden, omdat de trage "zoek"-stap volledig wordt overgeslagen.

Het Grote Plaatje: Waarom Dit Belangrijk Is

Het artikel beweert dat we door deze twee trucs te combineren verkiezingen veel sneller en goedkoper kunnen auditeren, zelfs in enorme staten met miljoenen kiezers.

Snelheid: In Californië duurde het uitvoeren van een volledige audit duizenden uren alleen al om de inventarislijst te maken. Met deze nieuwe methoden wordt die tijd drastisch ingekort.
Efficiëntie: Voor nauwe races (waar de winnaar wordt beslist door een klein fractie van een procent) vereisten de oude methoden het controleren van zoveel stembiljetten dat ze onpraktisch werden. De nieuwe "Directe Stembiljetselectie"-methode gaat veel beter om met deze nauwe races.
Flexibiliteit: Deze methoden werken of de stembiljetten nu in nette rijen liggen of in rommelige, door elkaar gehaalde stapels.

Kortom: De auteurs hebben een manier gevonden om te vertrouwen op een "ruwe schatting" van de inventaris en een "willekeurige greep" van stembiljetten, waarbij slimme wiskunde wordt gebruikt om aan te tonen dat deze shortcuts net zo veilig zijn als de oude, trage, "tel-alles"-methoden. Dit maakt het verifiëren van verkiezingsresultaten sneller, goedkoper en praktischer voor iedereen.

Technische Samenvatting: Sublineaire Risicogelimiteerde Audits via Directe Stembiljetselectie en Statistische Stembiljetmanifesten

1. Probleemstelling

Risicogelimiteerde audits (RLA's) zijn procedures na de verkiezingen die zijn ontworpen om strenge statistische garanties te bieden dat een incorrect verkiezingsuitslag met een waarschijnlijkheid die niet groter is dan een vooraf gespecificeerd risicolimiet ( $\alpha$ ), wordt gedetecteerd. Hoewel bestaande RLA's sterke beveiligingsgaranties bieden, staan ze voor twee kritieke knelpunten die hun efficiëntie en toepasbaarheid in diverse verkiezingsarchitecturen beperken:

Het Stembiljetmanifest-Knelpunt: Conventionele RLA's vereisen een "stembiljetmanifest"—een nauwkeurige, software-onafhankelijke verantwoording van de grootte van elke fysieke partij stembiljetten. Hoewel ruwe schattingen (bijvoorbeeld via wegen) eenvoudig te verkrijgen zijn, vereisen RLA's hoge nauwkeurigheid (fouten $\delta \ll \mu$ , waarbij $\mu$ de verkiezingsmarge is). Het bereiken van deze nauwkeurigheid vereist doorgaans een handmatige handtelling van elk stembiljet om het manifest te creëren. Dit proces schaalt lineair met het totale aantal stembiljetten ( $O(N)$ ), domineert vaak de totale audittijd en neutraliseert de efficiëntiewinsten van statistische steekproeven.
Het Indexeringsknelpunt bij Stembiljetvergelijking: De meest steekproefefficiënte RLA-methode is "stembiljetvergelijking", waarbij een willekeurig geselecteerd gestemd stemrecord (CVR) wordt gekoppeld aan het fysieke stembiljet. Dit vereist echter het efficiënt lokaliseren van een specifiek fysiek stembiljet op basis van een identificator. In moderne verkiezingsarchitecturen met voor de kiezer toegankelijke teltabellen worden stembiljetten expres gerandomiseerd om de privacy van de kiezer te waarborgen, waardoor de link tussen de volgorde van CVR's en de fysieke volgorde van stembiljetten wordt verbroken. Het lokaliseren van een specifiek stembiljet vereist dan een lineaire zoektocht door de partij (kostbaar) of een herberekening (kostbaar), waardoor rechtsgebieden gedwongen worden terug te vallen op minder efficiënte methoden zoals "stembiljetpeiling" of "partijvergelijking".

2. Methodologie

De auteurs stellen twee nieuwe technieken voor om deze knelpunten aan te pakken, waardoor sublineaire audit-efficiëntie mogelijk wordt over een breder spectrum aan verkiezingsconfiguraties.

A. Statistische Nauwkeurigheidscontrole voor Stembiljetmanifesten

In plaats van een volledige handtelling te vereisen om een manifest vast te stellen, stellen de auteurs een statistisch "bootstrapping"-mechanisme voor.

Gruwelijk Manifest: Auditors beginnen met een "grof" manifest verkregen via laag-effort bulkmethoden (bijvoorbeeld wegen), dat partijgroottes levert die nauwkeurig zijn binnen een grote factor $\Delta$ (bijvoorbeeld 10%).
Statistische Verificatie: De auditor gebruikt het grove manifest om partijen te bemonsteren met een waarschijnlijkheid die evenredig is met hun gerapporteerde (getelde) groottes. Voor elke bemonsterde partij voert de auditor een nauwkeurige handtelling uit om de ware grootte te verifiëren.
Certificering: Een statistische test bepaalt of de getelde groottes voldoende dicht bij de ware groottes liggen voor het overgrote deel van de stembiljetpopulatie. Als de test slaagt, wordt het grove manifest "geüpgraded" tot een statistisch gegarandeerd, hoog-nauwkeurig manifest zonder elk stembiljet te tellen. Dit verlaagt de kosten van manifestcreatie van $O(N)$ naar een sublineaire functie van $N$ .

B. Directe Stembiljetselectie (DBS)

Voor verkiezingsarchitecturen waarbij stembiljetten geen in-ordem identifiers ontberen (wat standaard stembiljetvergelijking verhindert), stellen de auteurs "Directe Stembiljetselectie" voor.

Omgekeerde Procedure: In tegenstelling tot standaard vergelijkingsaudits (waarbij een CVR wordt gekozen en het stembiljet wordt gevonden), kiest DBS een fysiek stembiljet uniform willekeurig uit een partij, leest de gedrukte identifier en vergelijkt deze met het overeenkomstige CVR.
Uitdaging Dubbelpuntdetectie: Deze omkering introduceert een nieuw risico: een adversary kan de CVR-tabel manipuleren door identifiers op te nemen die niet corresponderen met enig fysiek stembiljet (of door identifiers te dupliceren), waardoor detectie wordt ontweken.
Statistische Oplossing: De auteurs introduceren een nieuwe statistische test voor uniekheid van identifiers. Door stembiljetten te bemonsteren en te controleren op dubbele of ontbrekende identifiers, kan de audit de "excess identifier multiplicity rate" begrenzen. Als duplicaten voldoende zeldzaam zijn, behoudt de audit zijn risicolimiet.
Complexiteit: De steekproefcomplexiteit van DBS is asymptotisch $O\left(\frac{\log(1/\alpha)}{\mu}\right) + O\left(\sqrt{\frac{N \log(1/\alpha)}{\mu}}\right)$ . De tweede term (uniekheidstest) schaalt met $\sqrt{N}$ , afgeleid van het "verjaardagsparadox", wat aanzienlijk efficiënter is dan de lineaire zoektocht die door traditionele methoden in deze architecturen wordt vereist.

3. Belangrijkste Bijdragen

Statistisch Manifest Bootstrapping: Een methode om een laag-nauwkeurig, grof manifest om te zetten in een hoog-nauwkeurig, statistisch gecertificeerd manifest met sublineaire inspanning. Dit elimineert de noodzaak van exhaustieve handtellingen om het manifest vast te stellen.
Directe Stembiljetselectie (DBS): Een nieuwe klasse van RLA's die de standaard vergelijkingslogica omkeert om rekening te houden met voor de kiezer toegankelijke teltabellen met gerandomiseerde stembiljetvolgorde. Deze methode vermijdt lineaire zoektochten en herberekening.
Testen op Dubbele Identifiers: Een nieuwe statistische test geïntegreerd in de audit om het risico op duplicatie of weglating van identifiers te detecteren en te begrenzen, zodat de risicolimiet standhoudt zelfs bij directe bemonstering van fysieke stembiljetten.
Gefuseerd Kader: De integratie van deze technieken maakt een flexibele auditstrategie mogelijk waarbij de keuze van de methode (peiling, vergelijking of DBS) na de verkiezing kan worden gemaakt op basis van de waargenomen marge, in plaats van dat voorverkiezingsinfrastructuurbeslissingen vereist zijn.

4. Resultaten

De auteurs evalueerden hun technieken met behulp van simulaties gebaseerd op verkiezingsdata uit de VS (inclusief staten zoals Californië, Florida, Georgia en Connecticut) en diverse marges.

Manifest-efficiëntie:
- Voor een marge van 3% in Californië (16 miljoen stembiljetten) verminderde het gebruik van een statistisch nauwkeurig manifest de totale audittijd met een factor van 400 voor vergelijkingsaudits en 20 voor peilingsaudits in vergelijking met het aanmaken van een volledig handmatig manifest.
- Voor Directe Stembiljetselectie was de reductie een factor van 8, aangezien de methode nog steeds afhankelijk is van $N$ (hoewel gereduceerd tot $\sqrt{N}$ ) voor uniekheidstesten, terwijl vergelijking/peiling lineair afhankelijk zijn van $N$ voor manifestcreatie.
Steekproefcomplexiteit en Tijd:
- Kleine Marges: Voor een marge van 1% in Connecticut verminderde Directe Stembiljetselectie de vereiste steekproefgrootte van stembiljetten met 55% in vergelijking met de meest geavanceerde peilingsmethoden (Minerva/Providence).
- Congresdistricten: Voor marges tussen 0,5% en 1% verbeterde DBS peilingen met meer dan 75% in steekproefcomplexiteit.
- Schalbaarheid: De technieken zorgen ervoor dat de audittijd schaalt met de marge $\mu$ in plaats van gedomineerd te worden door de vaste kosten van manifestcreatie. Bijvoorbeeld, in een race met een marge van 2% in Georgia daalde de audittijd van 4.000 uur naar 1.200 uur door het gebruik van een statistisch manifest.

5. Betekenis en Claims

Het artikel stelt dat deze technieken een "opvallende reductie in de complexiteit van RLA's over een breed scala aan verkiezingsconfiguraties en marges" bieden.

Sublineaire Efficiëntie: De primaire betekenis is het bereiken van sublineaire efficiëntie in de totale auditinspanning. Door de behoefte aan een perfect manifest te ontkoppelen van de behoefte aan een volledige handtelling, en door efficiënte vergelijkingsaudits in gerandomiseerde omgevingen mogelijk te maken, betogen de auteurs dat RLA's praktisch kunnen worden ingezet in grootschalige verkiezingen zonder prohibitieve tijdkosten.
Software-onafhankelijkheid: De methoden behouden de kern-eigenschap van RLA's: software-onafhankelijkheid. De statistische tests voor manifestnauwkeurigheid en uniekheid van identifiers vertrouwen op fysieke stembiljettellingen en eenvoudige controles, waarbij geen vertrouwen nodig is in de interne logica van de teltabelsoftware.
Praktische Toepasbaarheid: De auteurs benadrukken dat deze methoden direct kunnen worden opgenomen in bestaande gestratificeerde RLA-kaders. Rechtsgebieden kunnen dynamisch de meest efficiënte methode kiezen (peiling, vergelijking of DBS) op basis van de specifieke marge van het contest, waardoor de toewijzing van middelen wordt geoptimaliseerd zonder beveiligingsgaranties op te offeren.

Het artikel concludeert dat hoewel asymptotische uitspraken intuïtie bieden, de expliciete numerieke resultaten aantonen dat deze technieken audits met hoge zekerheid haalbaar maken voor rechtsgebieden met grote populaties en krappe marges, waar eerdere methoden te traag waren (door manifestcreatie) of te steekproefintensief (door peilinginefficiënties).