💻 computer science

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

Dieser Beitrag stellt zwei neuartige risikobegrenzende Auditverfahren vor – eine statistische Methode zur Überprüfung von Stimmzettelmanifesten mit sublinearem Aufwand und einen direkten Ansatz zur Stimmzettauswahl –, die den für die Wahlprüfung erforderlichen Zeitaufwand und die Stichprobengröße erheblich reduzieren, insbesondere bei Wahlen mit knappen Ergebnissen.

Ursprüngliche Autoren: Benjamin Fuller, Abigail Harrison, Alexander Russell

Veröffentlicht 2026-05-19

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Benjamin Fuller, Abigail Harrison, Alexander Russell

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine Wahl wie eine riesige, chaotische Bibliothek vor, in der Millionen von Menschen gerade Bücher ausgeliehen haben (ihre Stimmen abgegeben haben). Das Computersystem der Bibliothek (der Zähler) druckt eine Liste aus, wer was ausgeliehen hat. Aber wie wissen wir, dass der Computer keinen Fehler gemacht hat oder schlimmer noch, gehackt wurde?

Hier kommen Risikobegrenzende Audits (RLAs) ins Spiel. Denken Sie an ein RLA als eine „Stichprobe", die mit hoher statistischer Sicherheit garantiert, dass der Wahlsieger korrekt ermittelt wurde. Wenn der Computer lügt, wird die Stichprobe ihn mit fast sicherer Wahrscheinlichkeit entlarven.

Die Durchführung dieser Stichproben wirft jedoch zwei riesige, kostspielige Probleme auf, die diese Arbeit löst:

Das „Inventarlisten"-Problem: Um die Bücher zu überprüfen, benötigen Sie eine perfekte Liste darüber, wie viele Bücher sich in jeder einzelnen Kiste (Batch) befinden. Eine solche Liste perfekt zu erstellen, bedeutet normalerweise, jedes einzelne Buch von Hand zu zählen, was den Zweck einer schnellen Stichprobe zunichte macht.
Das „Durchgemischtes Deck"-Problem: Bei vielen modernen Wahlmaschinen ist die Reihenfolge der physischen Stimmzettel absichtlich durcheinandergebracht, um die Privatsphäre der Wähler zu schützen. Dies macht es unglaublich schwierig, ein bestimmtes Buch im Regal zu finden, nur weil die Computerliste sagt: „Buch Nr. 4.502".

Die Autoren schlagen zwei neue „Magische Tricks" vor, um diese Probleme zu beheben, ohne jeden einzelnen Stimmzettel zählen zu müssen.

1. Der „Waage"-Trick (Statistische Manifeste)

Das Problem: Traditionell musste man, um der Inventarliste (dem „Manifest") zu vertrauen, jeden Stimmzettel in jeder Kiste zählen. Wenn die Liste angab, eine Kiste enthalte 100 Stimmzettel, musste man 100 zählen, um sicher zu sein. Wenn man auch nur um einen winzigen Betrag danebenlag, konnte das gesamte Audit verworfen werden.

Die Lösung: Die Autoren schlagen vor, zunächst eine „grobe Schätzung" zu verwenden, ähnlich wie das Wiegen einer Kiste voller Bücher. Man weiß, dass eine Kiste mit 100 Büchern ungefähr 10 Pfund wiegt. Man muss sie nicht zählen, um zu wissen, dass es ungefähr 100 sind.

Die Metapher: Stellen Sie sich vor, Sie haben 1.000 Kisten voller Bücher. Statt jede Kiste zu öffnen und zu zählen, wiegen Sie sie alle. Sie erhalten eine „grobe" Liste, die zu 90 % genau ist.
Die Magie: Die Autoren haben einen statistischen Test entwickelt, der diese „grobe" Liste nutzt, um die „perfekte" Liste des Computers zu verifizieren. Sie wählen zufällig einige Kisten aus, wiegen sie und zählen dann tatsächlich die Bücher nur in diesen wenigen. Wenn die Zählung innerhalb eines winzigen Fehlerspielraums mit der Behauptung des Computers übereinstimmt, „bootstrapt" (hebt) der Test die grobe Schätzung zu einer vertrauenswürdigen, hochgenauen Liste.
Das Ergebnis: Sie müssen nicht jeden Stimmzettel zählen, um eine vertrauenswürdige Liste zu erhalten. Sie zählen nur einen kleinen Bruchteil. Für einen riesigen Staat wie Kalifornien reduziert dies die Zeit zur Vorbereitung der Audit-Liste um einen Faktor von 400.

2. Der „Umgekehrte Such"-Trick (Direkte Stimmzettauswahl)

Das Problem: Normalerweise läuft ein Audit so ab: Der Computer sagt: „Überprüfen Sie den Stimmzettel mit der ID #999." Der Auditor muss dann durch einen unordentlichen Korb mit tausenden durcheinandergewürfelten Stimmzetteln jagen, um den mit der ID #999 zu finden. Diese „Suche" ist langsam und teuer.

Die Lösung: Die Autoren drehen den Spieß um. Anstatt einen bestimmten Stimmzettel basierend auf einer Computer-ID zu finden, nehmen sie einfach einen zufälligen physischen Stimmzettel aus einer Kiste, lesen seine ID und fragen dann den Computer: „Was hast du gesagt, dieser Stimmzettel hat gewählt?"

Die Metapher: Anstatt nach einer bestimmten Nadel im Heuhaufen zu suchen, greifen Sie einfach eine Handvoll Heu, schauen sich die Nadeln an, die Sie gefunden haben, und prüfen, ob sie mit der Liste übereinstimmen.
Der Haken: Wenn der Computer lügt und auf seiner Liste „gefälschte" IDs (doppelte Nummern) hat, die auf keinem echten Stimmzettel existieren, könnte diese Methode getäuscht werden.
Die Korrektur: Die Autoren fügten einen zweiten statistischen Test hinzu, um auf „gefälschte Nadeln" zu prüfen. Sie zählen, wie oft sie dieselbe ID bei ihrem zufälligen Griff zweimal sehen. Wenn Duplikate selten sind (was sie sein sollten), ist das Audit sicher.
Das Ergebnis: Diese Methode ist bei kleinen Wahlergebnissen (knappen Rennen) viel schneller. Für ein knappes Rennen in Connecticut ist diese Methode 55 % schneller als die derzeit besten Methoden, da sie den langsamen „Such"-Schritt vollständig überspringt.

Das große Ganze: Warum dies wichtig ist

Die Arbeit behauptet, dass wir durch die Kombination dieser beiden Tricks Wahlen viel schneller und günstiger auditen können, selbst in riesigen Staaten mit Millionen von Wählern.

Geschwindigkeit: In Kalifornien dauerte ein vollständiges Audit früher Tausende von Stunden nur für die Erstellung der Inventarliste. Mit diesen neuen Methoden wird diese Zeit drastisch verkürzt.
Effizienz: Bei knappen Rennen (bei denen der Gewinner durch einen winzigen Bruchteil eines Prozentsatzes entschieden wird) erforderten die alten Methoden die Überprüfung so vieler Stimmzettel, dass sie unpraktisch wurden. Die neue „Direkte Stimmzettauswahl"-Methode bewältigt diese knappen Rennen viel besser.
Flexibilität: Diese Methoden funktionieren unabhängig davon, ob die Stimmzettel in ordentlichen Reihen oder in unordentlichen, durcheinandergewürfelten Stapeln liegen.

Kurz gesagt: Die Autoren haben einen Weg gefunden, einer „grobe Schätzung" des Inventars und einem „zufälligen Griff" nach Stimmzetteln zu vertrauen, indem sie clevere Mathematik verwenden, um nachzuweisen, dass diese Abkürzungen genauso sicher sind wie die alten, langsamen „alles-zählen"-Methoden. Dies macht die Überprüfung von Wahlergebnissen für alle schneller, günstiger und praktikabler.

Technische Zusammenfassung: Sublineare risikobegrenzende Audits durch direkte Stimmzetauswahl und statistische Stimmzettelmanifeste

1. Problemstellung

Risikobegrenzende Audits (RLAs) sind Nachwahlverfahren, die entwickelt wurden, um strenge statistische Garantien zu bieten, dass ein fehlerhaftes Wahlergebnis mit einer Wahrscheinlichkeit erkannt wird, die einen vorab festgelegten Risikogrenzwert ( $\alpha$ ) nicht überschreitet. Obwohl bestehende RLAs starke Sicherheitsgarantien bieten, stehen sie vor zwei kritischen Engpässen, die ihre Effizienz und Anwendbarkeit über diverse Wahlarchitekturen hinweg einschränken:

Der Stimmzettelmanifest-Engpass: Herkömmliche RLAs erfordern ein „Stimmzettelmanifest" – eine genaue, softwareunabhängige Erfassung der Größe jeder physischen Partie von Stimmzetteln. Während grobe Schätzungen (z. B. durch Wägen) leicht zu erhalten sind, erfordern RLAs eine hohe Genauigkeit (Fehler $\delta \ll \mu$ , wobei $\mu$ der Wahlabstand ist). Das Erreichen dieser Genauigkeit erfordert typischerweise eine manuelle Handzählung jedes einzelnen Stimmzettels zur Erstellung des Manifests. Dieser Prozess skaliert linear mit der Gesamtzahl der Stimmzettel ( $O(N)$ ), dominiert oft die gesamte Auditzeit und zunichtemacht die Effizienzgewinne des statistischen Stichprobenverfahrens.
Der Indexierungs-Engpass beim Stimmzettelvergleich: Die stichproben-effizienteste RLA-Methode ist der „Stimmzettelvergleich", bei dem ein zufällig ausgewählter Stimmzettel-Eintrag (Cast Vote Record, CVR) mit seinem physischen Stimmzettel abgeglichen wird. Dies erfordert jedoch die effiziente Lokalisierung eines spezifischen physischen Stimmzettels basierend auf einer Kennung. In modernen Wahlarchitekturen, die wählerzugewandte Auszählgeräte verwenden, werden Stimmzettel absichtlich randomisiert, um die Privatsphäre der Wähler zu schützen, wodurch die Verbindung zwischen der Reihenfolge der CVRs und der physischen Reihenfolge der Stimmzettel unterbrochen wird. Die Lokalisierung eines spezifischen Stimmzettels erfordert dann entweder eine lineare Suche durch die Partie (kostspielig) oder eine Neu-Auszählung (kostspielig), was die Gerichtsbarkeiten zwingt, zu weniger effizienten Methoden wie „Stimmzettel-Polling" oder „Partievergleich" zurückzukehren.

2. Methodik

Die Autoren schlagen zwei neuartige Techniken vor, um diese Engpässe zu adressieren und eine sublineare Audit-Effizienz über ein breiteres Spektrum von Wahlkonfigurationen hinweg zu ermöglichen.

A. Statistische Genauigkeitsprüfung für Stimmzettelmanifeste

Anstatt eine vollständige Handzählung zur Erstellung eines Manifests zu erfordern, schlagen die Autoren einen statistischen „Bootstrapping"-Mechanismus vor.

Grobes Manifest: Die Auditoren beginnen mit einem „groben" Manifest, das durch aufwendigkeitsarme Massmethoden (z. B. Wägen) gewonnen wird und Partiegroßen liefert, die innerhalb eines großen Faktors $\Delta$ (z. B. 10 %) genau sind.
Statistische Verifizierung: Der Auditor verwendet das grobe Manifest, um Partien mit einer Wahrscheinlichkeit proportional zu ihren gemeldeten (ausgezählten) Größen zu beproben. Für jede beprobte Partie führt der Auditor eine präzise Handzählung durch, um die wahre Größe zu verifizieren.
Zertifizierung: Ein statistischer Test bestimmt, ob die ausgezählten Größen für die überwiegende Mehrheit der Stimmzettel-Population ausreichend nahe an den wahren Größen liegen. Wenn der Test bestanden wird, wird das grobe Manifest zu einem statistisch garantierten, hochgenauen Manifest „aufgewertet", ohne jeden Stimmzettel zu zählen. Dies reduziert die Kosten für die Manifesterstellung von $O(N)$ auf eine sublineare Funktion von $N$ .

B. Direkte Stimmzettauswahl (DBS)

Für Wahlarchitekturen, bei denen Stimmzettel keine in-Reihenfolge-Kennungen besitzen (was einen standardmäßigen Stimmzettelvergleich verhindert), schlagen die Autoren die „Direkte Stimmzettauswahl" (Direct Ballot Selection, DBS) vor.

Umgekehrtes Verfahren: Im Gegensatz zu Standard-Vergleichsaudits (bei denen ein CVR ausgewählt und der Stimmzettel gefunden wird), wählt DBS einen physischen Stimmzettel gleichverteilt zufällig aus einer Partie aus, liest seine aufgedruckte Kennung und vergleicht sie mit dem entsprechenden CVR.
Herausforderung der Duplikaterkennung: Diese Umkehrung führt ein neues Risiko ein: Ein Angreifer könnte die CVR-Tabelle manipulieren, indem er Kennungen einschließt, die keinem physischen Stimmzettel entsprechen (oder Kennungen dupliziert), und so der Entdeckung entgeht.
Statistische Lösung: Die Autoren führen einen neuen statistischen Test auf die Einzigartigkeit von Kennungen ein. Durch das Beproben von Stimmzetteln und das Prüfen auf doppelte oder fehlende Kennungen kann das Audit die „Rate der übermäßigen Kennungsmultiplizität" begrenzen. Wenn Duplikate hinreichend selten sind, bleibt das Risikolimit des Audits erhalten.
Komplexität: Die Stichprobengröße von DBS ist asymptotisch $O\left(\frac{\log(1/\alpha)}{\mu}\right) + O\left(\sqrt{\frac{N \log(1/\alpha)}{\mu}}\right)$ . Der zweite Term (Einzigartigkeitstest) skaliert mit $\sqrt{N}$ , abgeleitet aus dem „Geburtstagsparadoxon", was erheblich effizienter ist als die lineare Suche, die von traditionellen Methoden in diesen Architekturen erfordert wird.

3. Hauptbeiträge

Statistisches Manifest-Bootstrapping: Eine Methode, um ein ungenaueres, grobes Manifest in ein hochgenaues, statistisch zertifiziertes Manifest mit sublinearem Aufwand zu verwandeln. Dies eliminiert die Notwendigkeit einer erschöpfenden Handzählung zur Erstellung des Manifests.
Direkte Stimmzettauswahl (DBS): Eine neue Klasse von RLAs, die die Standard-Vergleichslogik umkehrt, um wählerzugewandte Auszählgeräte mit randomisierten Stimmzettelreihenfolgen zu unterstützen. Diese Methode vermeidet lineare Suchen und Neu-Auszählungen.
Test auf doppelte Kennungen: Ein neuartiger statistischer Test, der in das Audit integriert ist, um das Risiko der Duplizierung oder des Auslassens von Kennungen zu erkennen und zu begrenzen, wodurch sichergestellt wird, dass das Risikolimit auch beim direkten Beproben physischer Stimmzettel gilt.
Einheitlicher Rahmen: Die Integration dieser Techniken ermöglicht eine flexible Audit-Strategie, bei der die Wahl der Methode (Polling, Vergleich oder DBS) nach der Wahl basierend auf dem beobachteten Abstand getroffen werden kann, anstatt vor der Wahl getroffene Infrastrukturentscheidungen zu erfordern.

4. Ergebnisse

Die Autoren bewerteten ihre Techniken mittels Simulationen auf Basis von US-Wahldaten (einschließlich Bundesstaaten wie Kalifornien, Florida, Georgia und Connecticut) und verschiedener Abstandsgrößen.

Manifest-Effizienz:
- Bei einem 3 %-Abstand in Kalifornien (16 Mio. Stimmzettel) reduzierte die Verwendung eines statistisch genauen Manifests die gesamte Auditzeit um den Faktor 400 für Vergleichsaudits und um den Faktor 20 für Polling-Audits im Vergleich zur Erstellung eines vollständigen manuellen Manifests.
- Bei der Direkten Stimmzettauswahl betrug die Reduktion den Faktor 8, da die Methode für den Einzigkeitstest immer noch von $N$ abhängt (wenn auch reduziert auf $\sqrt{N}$ ), während Vergleich/Polling für die Manifesterstellung linear von $N$ abhängen.
Stichprobengröße und Zeit:
- Kleine Abstände: Bei einem 1 %-Abstand in Connecticut reduzierte die Direkte Stimmzettauswahl die erforderliche Stimmzettel-Stichprobengröße um 55 % im Vergleich zu modernen Polling-Methoden (Minerva/Providence).
- Kongressbezirke: Bei Abständen zwischen 0,5 % und 1 % verbesserte DBS das Polling in Bezug auf die Stichprobengröße um über 75 %.
- Skalierbarkeit: Die Techniken ermöglichen es, dass die Auditzeit mit dem Abstand $\mu$ skaliert, anstatt von den fixen Kosten der Manifesterstellung dominiert zu werden. Beispielsweise sank die Auditzeit bei einem Rennen mit 2 %-Abstand in Georgia von 4.000 Stunden auf 1.200 Stunden durch die Verwendung eines statistischen Manifests.

5. Bedeutung und Behauptungen

Die Arbeit behauptet, dass diese Techniken eine „bemerkenswerte Reduzierung der Komplexität von RLAs über einen weiten Bereich von Wahlkonfigurationen und Abständen" bieten.

Sublineare Effizienz: Die primäre Bedeutung liegt im Erreichen einer sublinearen Effizienz beim gesamten Audit-Aufwand. Durch die Entkopplung des Bedarfs an einem perfekten Manifest vom Bedarf an einer vollständigen Handzählung und durch die Ermöglichung effizienter Vergleichsaudits in randomisierten Umgebungen argumentieren die Autoren, dass RLAs in großangelegten Wahlen ohne prohibitiv hohe Zeitkosten praktisch eingesetzt werden können.
Softwareunabhängigkeit: Die Methoden bewahren die Kern-Eigenschaft der RLAs, die Softwareunabhängigkeit. Die statistischen Tests auf Manifestgenauigkeit und Kennungseinzigartigkeit beruhen auf physischen Stimmzettelzählungen und einfachen Prüfungen und erfordern kein Vertrauen in die interne Logik der Auszählsoftware.
Praktische Anwendbarkeit: Die Autoren betonen, dass diese Methoden sofort in bestehende geschichtete RLA-Rahmenwerke integriert werden können. Gerichtsbarkeiten können dynamisch die effizienteste Methode (Polling, Vergleich oder DBS) basierend auf dem spezifischen Abstand des Wettbewerbs wählen und so die Ressourcenallokation optimieren, ohne Sicherheitsgarantien zu opfern.

Die Arbeit schließt, dass zwar asymptotische Aussagen Intuition liefern, die expliziten numerischen Ergebnisse jedoch zeigen, dass diese Techniken ein hochsicheres Auditieren für Gerichtsbarkeiten mit großer Bevölkerung und enge Abstände machbar machen, bei denen frühere Methoden entweder zu langsam (aufgrund der Manifesterstellung) oder zu stichprobenintensiv (aufgrund von Polling-Ineffizienzen) waren.