Punchscan

Punchscan
Utvecklare	Richard Carback, David Chaum , Jeremy Clark, Aleks Essex och Stefan Popoveniuc.
Stabil frisättning	1.0 (2 november 2006)
Förhandsgranska release	1,5 (16 juli 2007)
Skrivet i	Java
Operativ system	Cross-plattform
Tillgänglig i	engelsk
Typ	rösträkningssystem
Licens	Reviderad BSD-licens
Hemsida	http://punchscan.org/

Punchscan är ett rösträkningssystem för optisk skanning som uppfunnits av kryptografen David Chaum . Punchscan är designat för att erbjuda integritet, integritet och transparens. Systemet kan verifieras av väljare, tillhandahåller en end-to-end (E2E) revisionsmekanism och utfärdar ett röstkvitto till varje väljare. Systemet vann det stora priset vid 2007 års universitetsröstningssystemtävling .

Datormjukvaran som Punchscan innehåller är öppen källkod ; källkoden släpptes den 2 november 2006 under en reviderad BSD- licens . Punchscan är dock mjukvaruoberoende; den hämtar sin säkerhet från kryptografiska funktioner istället för att förlita sig på mjukvarusäkerhet som DRE-röstningsmaskiner . Av denna anledning kan Punchscan köras på operativsystem med sluten källkod, som Microsoft Windows , och fortfarande upprätthålla ovillkorlig integritet.

Punchscan-teamet, med ytterligare bidragsgivare, har sedan dess utvecklat Scantegrity .

Röstningsförfarande

En märkt Punchscan-röstsedel. Full valsedel (överst), separerad valsedel (nederst).

En Punchscan- valsedel har två lager papper. På det översta lagret listas kandidaterna med en symbol eller bokstav bredvid deras namn. Under kandidatlistan finns en rad runda hål i valsedelns översta lager. Inuti hålen på bottenlagret är motsvarande symboler tryckta.

För att rösta på en kandidat måste väljaren lokalisera hålet med symbolen som motsvarar symbolen bredvid kandidatens namn. Det här hålet är markerat med en i bingostil , som är avsiktligt större än hålet. Väljaren separerar sedan valsedeln, väljer antingen det översta eller nedersta lagret att behålla som kvitto och river sönder det andra lagret. Kvittot skannas i vallokalen för tabulering .

Ordningen på symbolerna bredvid kandidatnamnen genereras slumpmässigt för varje valsedel, och skiljer sig därför från valsedel till valsedel. Likaså för ordningen på symbolerna i hålen. Av denna anledning innehåller inte kvittot tillräckligt med information för att avgöra vilken kandidat rösten avgavs på. Om det översta lagret behålls är ordningen på symbolerna genom hålen okänd. Om det nedre lagret behålls är ordningen på symbolerna bredvid kandidatens namn okänd. Därför kan väljaren inte bevisa för någon annan hur de röstat, vilket förhindrar röstköp eller väljarskräm.

Tabuleringsförfarande

Som ett exempel, betrakta ett tvåkandidatval mellan Coke och Pepsi , som illustreras i föregående diagram. Ordningen på bokstäverna bredvid kandidaternas namn kan vara A och sedan B, eller B och sedan A. Vi kommer att kalla denna ordning ${\displaystyle P_{1}} ,$ och låta $P_{1}$ =0 för den förra beställningen och $P_{1}$ =1 för den senare. Därför,

$P_{1}$ : ordning av symboler bredvid kandidatlistan,

P_{1}\in \{0,1\}=\{{\mbox{AB}},{\mbox{BA}}\}\ ,

.

På samma sätt kan vi generalisera för andra delar av en valsedel:

$P_{2}$ : ordning av symboler genom hålen,

P_{2}\in \{0,1\}=\{{\mbox{AB}},{\mbox{BA}}\}\ ,

.

$P_{3}$ : vilket hål är markerat,

P_{3}\in \{0,1\}=\{{\mbox{1st}},{\mbox{2nd}}\}\ ,

.

$R$ : resultatet av omröstningen,

R\in \{0,1\}=\{{\mbox{Coke}},{\mbox{Pepsi}}\}\,

.

Observera att ordningen på kandidaternas namn är fast över alla valsedlar. Resultatet av en omröstning kan beräknas direkt som,

R=P_{1}+P_{2}+P_{3}{\bmod {2}}\,

( Ekvation 1 )

Men när ett lager av valsedeln strimlas förstörs antingen $P_{1}$ eller ${\displaystyle P_{2}} .$ Därför finns det inte tillräckligt med information för att beräkna $R$ från kvittot (som skannas). För att beräkna valresultatet används en elektronisk databas .

Inför valet skapas databasen med en rad kolumner som sådan. Varje rad i databasen representerar en omröstning, och ordningen som valsedlarna lagras i databasen blandas ( med en kryptografisk nyckel som varje kandidat kan bidra till ). Den första kolumnen, $D_{1}$ , har den blandade ordningen för serienumren. $D_{2}$ innehåller en pseudoslumpmässig bitström genererad från nyckeln, och den kommer att fungera som ett strömchiffer . $D_{3}$ lagrar ett mellanresultat. $D_{4}$ innehåller en bit så att:

D_{2}+D_{4}=P_{1}+P_{2}{\bmod {2}}\,

Resultatet av varje omröstning kommer att lagras i en separat kolumn, $R$ , där ordningen på valsedlarna kommer att blandas om igen. ${\displaystyle D_{5}} innehåller$ alltså radnumret i kolumnen $R$ där resultatet kommer att placeras.

Efter att valet genomförts och $P_{3}$ -värdena har skannats in, beräknas ${\displaystyle D_{3}} som:$

D_{3}=P_{3}+D_{2}{\bmod {2}}\,

Och resultatet beräknas som,

R=D_{3}+D_{4}{\bmod {2}}\,

Detta motsvarar ekvation 1,

{\begin{aligned}R&=(D_{3})+D_{4}{\bmod {2}}\\&=(P_{3}+D_{2})+D_{4}{ \bmod {2}}\\&=P_{3}+(D_{2}+D_{4}){\bmod {2}}\\&=P_{3}+(P_{1}+P_{ 2}){\bmod {2}}\end{aligned}}

Resultatkolumnen publiceras och med tanke på att röstsedlarna har blandats (två gånger) så anger inte resultatkolumnens ordning vilket resultat som kommer från vilket röstnummer. Valmyndigheten kan alltså inte spåra röster till löpnummer.

Generaliserad form

För ett val med $n$ kandidater, följs ovanstående procedur med modulo -n ekvationer.

Grundläggande revisionsrutiner

Väljarens röstkvitto anger inte vilken kandidat väljaren röstat på och det är därför inte hemlig information. Efter ett val kommer valmyndigheten att lägga ut en bild på varje kvitto på nätet. Väljaren kan slå upp sin röstsedel genom att skriva in löpnumret och de kan kontrollera att uppgifter som valmyndigheten har stämmer överens med deras röstsedel. På så sätt kan väljaren vara säker på att deras röst har avgivits som avsett .

Alla väljare eller intresserade kan också inspektera en del av databasen för att säkerställa att resultaten beräknades korrekt. De kan inte inspektera hela databasen, annars kan de koppla röster till röstsedlarnas serienummer. Hälften av databasen kan dock säkert inspekteras utan att inkräkta på integriteten. Ett slumpmässigt val görs mellan att öppna $\{D_{1},D_{2},D_{3}\}$ eller $\{D_{3},D_{4},D_{5}\}$ (det här valet kan härledas från den hemliga nyckeln eller från en sann slumpmässig källa, såsom tärningar eller börsen ). Detta förfarande gör att väljaren kan vara säker på att uppsättningen av alla röstsedlar räknades som avgivna .

Om alla röster räknas som avgivna och avgivna som avsett , så räknas alla röster som avsett . Därför kan valets integritet bevisas med mycket stor sannolikhet.

Ytterligare säkerhet

För att ytterligare öka integriteten i ett Punchscan-val kan flera ytterligare steg tas för att skydda mot en helt korrupt valmyndighet.

Flera databaser

Eftersom $D_{1}$ , $D_{2}$ och $D_{5}$ i databasen alla genereras pseudoslumpmässigt, kan flera databaser skapas med olika slumpmässiga värden för dessa kolumner. Varje databas är oberoende av de andra, vilket gör att den första hälften av några av databaserna kan öppnas och inspekteras och den andra hälften av andra. Varje databas måste producera samma slutliga sammanställning. Om en valmyndighet skulle manipulera databasen för att förvränga den slutliga räkningen, skulle de alltså behöva manipulera med var och en av databaserna. Sannolikheten för att manipuleringen ska avslöjas i granskningen ökar med antalet oberoende databaser.

Åtaganden

Inför ett val skriver valmyndigheten ut valsedlarna och skapar databasen/databaserna. En del av denna skapelseprocess innebär att man förbinder sig till den unika information som finns på varje valsedel och i databaserna. Detta åstadkoms genom att tillämpa en kryptografisk envägsfunktion på informationen. Även om resultatet av denna funktion, åtagandet, offentliggörs, förblir den faktiska informationen som åtagit sig att vara förseglad. Eftersom funktionen är enkelriktad är det beräkningsmässigt omöjligt att fastställa informationen på den förseglade valsedeln endast med tanke på dess offentligt publicerade åtagande.

Valsedelinspektion

Inför ett val produceras dubbelt så många valsedlar som det antal som är tänkt att användas i valet. Hälften av dessa valsedlar väljs ut slumpmässigt (eller varje kandidat kan välja en bråkdel av valsedlarna) och öppnas. Raderna i databasen som motsvarar dessa valda valsedlar kan kontrolleras för att säkerställa att beräkningarna är korrekta och inte manipuleras. Eftersom valmyndigheten inte på förhand vet vilka valsedlar som kommer att väljas, innebär en godkänd revision att databasen är välformad med mycket hög sannolikhet. Vidare kan röstsedlarna kontrolleras mot sina åtaganden för att med stor sannolikhet säkerställa att röståtagandena är korrekta.

Se även

externa länkar

Projektets hemsida
Vocomp Submission — ett omfattande dokument på 80 sidor som förklarar alla aspekter av systemet
Electronic Democracy — BBC Worlds Digital Planet- ljudintervju med David Chaum .
Att få varje e-röst att räknas – IEEE Spectrum .
Transparent och öppen röstning med Punchscan: Del I och Del II
Future Tense ljudintervju med David Chaum .