technology
from seed
VeryVote
A Voter Verifiable Code Voting System
Rui Joaquim
[email protected] (INESC-ID \ ISEL)
Carlos Ribeiro [email protected] (INESC-ID \ IST)
Paulo Ferreira [email protected] (INESC-ID \ IST)
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
Grupo de Sistemas Distribuídos
technology
Introduction
from seed
• VeryVote is an Internet voting system.
• Internet voting:
(+) brings more convenience to voters, allowing to vote from
anywhere with an Internet connection.
(–) suffers from the secure platform problem.
• The client platform is not controlled nor trustworthy.
• How to guarantee the election integrity in this setup?
(–) vote buying and coercion issues inherent to remote voting.
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
2
technology
from seed
VeryVote Overview
•
VeryVote addresses the secure platform problem.
•
VeryVote uses a code voting approach.
– Prevents the misbehavior of the not trusted client platform.
– However, it “does not” provide mechanisms to verify if the vote is counted as
intended by the voter.
•
VeryVote vote protocol is a fusion between a generic code voting protocol and
the MarkPledge technique.
– Cast-as-intended voter verification.
– Universal count-as-cast verification.
end-to-end verifiability.
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
3
technology
from seed
The Problem
Voter
Election Server
Vote A
Thank you!
APP
Tally
A
B
Vote B
Voter’s PC
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
4
technology
from seed
Generic Code Voting Approach
Voter
Election Server
Code Sheet
Vote codes
A – 3WQ
B – M8W
C – WAM
…
Confirmation code
3WQ
JRF
•
•
How we can verify the tally?
Publishing the received vote codes and
associated candidates.
–
–
–
•
Tally
JRF
A
B
Each voter can verify her vote.
Anyone can do the vote count.
But, the voter cannot correct her vote.
The election tally is already published!!!
APP
Voter’s PC
Is there a better way?
–
Yes, VeryVote.
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
5
technology
from seed
MarkPledge Overview
•
MarkPledge is a cut-and-choose technique proposed to provide cast-as-intended
verification to poll station voting, and works based on two functions: BitEnc(b) and
OpenBitEnc(BitEnc(b), challenge).
BitEnc(0) =
A3C
53W 8F9
324
SQ1 DHJ
IPS
E9F
287
KJL
FXC ZPT
BitEnc(1) =
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
encrypted value
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
6
technology
from seed
MarkPledge Overview
•
MarkPledge is a cut-and-choose technique proposed to provide cast-as-intended
verification to poll station voting, and works based on two functions: BitEnc(b) and
OpenBitEnc(BitEnc(b), challenge).
BitEnc(0) =
A3C
53W 8F9
324
SQ1 DHJ
IPS
E9F
287
KJL
FXC ZPT
BitEnc(1) =
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
encrypted value
decrypted value
c1
OpenBitEnc( BitEnc(0), c1 ) = SQ1
OpenBitEnc( BitEnc(1), c1 ) = JRF
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
7
technology
from seed
MarkPledge Overview
•
MarkPledge is a cut-and-choose technique proposed to provide cast-as-intended
verification to poll station voting, and works based on two functions: BitEnc(b) and
OpenBitEnc(BitEnc(b), challenge).
BitEnc(0) =
A3C
53W 8F9
324
SQ1 DHJ
IPS
E9F
287
KJL
FXC ZPT
BitEnc(1) =
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
encrypted value
decrypted value
c2
c1
OpenBitEnc( BitEnc(0), c1 ) = SQ1
OpenBitEnc( BitEnc(1), c1 ) = JRF
OpenBitEnc( BitEnc(0), c2 ) = IPS
OpenBitEnc( BitEnc(1), c2 ) = JRF
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
8
technology
from seed
MarkPledge Overview
•
MarkPledge is a cut-and-choose technique proposed to provide cast-as-intended
verification to poll station voting, and works based on two functions: BitEnc(b) and
OpenBitEnc(BitEnc(b), challenge).
BitEnc(0) =
A3C
53W 8F9
324
SQ1 DHJ
IPS
E9F
287
KJL
FXC ZPT
BitEnc(1) =
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
JRF
encrypted value
c2
decrypted value
OpenBitEnc( BitEnc(0), c2 ) = IPS
OpenBitEnc( BitEnc(1), c2 ) = JRF
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
9
technology
MarkPledge Vote/Receipt Verification
Poll station voting (inside the voting booth)
Voter
from seed
Printer
Vote Machine
JRF
Random
Commit
challenge
Bob to c (c)
MarkPledge Vote/Receipt
Candidates
Vote Encryption
(BitEnc)
Vote Receipt
(OpenBitEnc)
BitEnc(0)
Alice the election
W3E
After
end:
BitEnc(1)
JRF
1.Bob The Vote
MachineJRF
publishes the
MarkPledge
vote/receipts. R59
BitEnc(0)
Charles
2.Dino External organizations
verify KMZ
the
BitEnc(0)
correctness of the published data.
Challenge = c
3.
The voter verify her receipt (and correct
her vote if necessary).
4.
The votes are tallied using a protocol
with counted-as-cast verification.
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
10
technology
Building Blocks And VeryVote
Protocol Overview
Generic code
voting
Verifiability /
Election integrity
Voter interaction
(while voting)
from seed
MarkPledge
VeryVote
• Prevents APP vote
manipulations.
• End-to-end verifiable.
• End-to-end verifiable.
Tricky
• 3 inputs (total).
• 2 non trivial inputs.
• Step order must be respected.
• Requires a printer while voting.
Simple
• Only one input.
• Election server can
manipulate the tally.
Simple
• Only one input.
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
11
technology
Election Preparation
1.
A set of trustees create a threshold shared election key pair.
2.
The Election Server (ES) pre-computes and commits to the votes to
be used in the election.
•
The BitEnc(b) constructions are built using the election public key.
from seed
Pre-computed Vote
BitEnc(0)
BitEnc(0)
BitEnc(1)JRF
BitEnc(0)
Code Sheet
3.
The code sheets are created and associated to a pre-computed vote.
•
The confirmation code is the value encrypted in the elements of the
BitEnc(1) construction.
Vote codes
Alice – 3WQ
Bob – M8W
Charles – WAM
Dino – QGH
Confirmation code
JRF
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
12
technology
Election Preparation
4.
from seed
The code sheets are distributed to the voters:
•
Anonymous distribution
+ ES does not know who the voters are (more privacy guarantees).
– Allows the ES to add votes for the voters that did not vote.
•
Non anonymous distribution
+ Easier distribution process.
+ Prevents or makes detectable the addition of votes.
– The ES knows who voted for who.
5.
Just before the election, the trustees create and announce a Shared
Random Election Value (SREV)
•
•
The SREV value is not known at the creation time of the pre-computed votes.
The SREV will be used as a random source in the challenge generation process.
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
13
technology
from seed
VeryVote Vote Protocol
Voter
Election Server
Code Sheet
Vote codes
Alice – 3WQ
Bob – M8W
Charles – WAM
Dino – QGH
Vote Receipt
3WQ
Confirmation code
Alice – JRF
Bob – I5W
Charles – JCU
Dino – KAI
JRF
After the election end:
1.
The ES publishes all the pre-computed votes and
corresponding Final Votes and receipts.
2.
The trustees verify the correctness of the published
data.
3.
The voters confirm their receipts with the verified
receipts. If any error is detected they make correct
vote, because the election tally is not yet published.
4.
Pre-computed Vote
BitEnc(0)
BitEnc(0)
BitEnc(1)JRF
BitEnc(0)
Final Vote
APP
BitEnc(1)JRF
BitEnc(0)
BitEnc(0)
BitEnc(0)
Voter’s PC
challenge = hash(
, SREV)
After the claiming stage, the votes are anonymized
by a mix net and decrypted by the trustees.
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
14
technology
from seed
VeryVote Integrity Quick analysis
Voter
Election Server
Code Sheet
Vote codes
Alice – 3WQ
Bob – M8W
Charles – WAM
Dino – QGH
Confirmation code
JRF
•
Vote Receipt
3WQ
Alice – JRF
Bob – I5W
Charles – JCU
Dino – KAI
BitEnc(0)
BitEnc(0)
BitEnc(1)JRF
BitEnc(0)
The APP “cannot” modify the voter’s choice because
it does not know the vote codes.
Final Vote
APP
•
The ES “cannot” modify the voter’s choice because
the process changes the vote receipt.
Pre-computed Vote
BitEnc(1)JRF
BitEnc(0)
BitEnc(0)
BitEnc(0)
Voter’s PC
challenge = hash(
, SREV)
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
15
technology
from seed
VeryVote Integrity Quick analysis
Voter
Election Server
Code Sheet
Vote codes
Alice – 3WQ
Bob – M8W
Charles – WAM
Dino – QGH
Confirmation code
KJE
•
Vote Receipt
3WQ
Alice – KJE
Bob – JRF
Charles – JCU
Dino – KAI
BitEnc(0)
BitEnc(0)
BitEnc(1)JRF
BitEnc(0)
The ES can create a fake receipt if it can find the right
permutation of the BitEnc(b) values.
–
The probability of this happening is approximately
Final Vote
APP
P1 = n! / #CC
–
This probability can be made constant if we generate
the challenge from the Pre-Computed Vote.
Pre-computed Vote
BitEnc(0)
BitEnc(1)JRF
BitEnc(0)
BitEnc(0)
Voter’s PC
P2 = (n – 1) / #CC
challenge = hash(
, SREV)
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
16
technology
from seed
Conclusions
•
VeryVote provides end-to-end verifiability in the Internet voting scenario.
–
–
•
VeryVote successfully addresses one of the most important problems of remote
electronic voting.
–
•
The secure platform problem.
VeryVote has a simple voter interaction, and therefore is very appealing for real use.
–
•
The voter can privately verify and correct her vote before the tally publication.
The tally process is verifiable.
To the eyes of the voter, the VeryVote protocol is very similar to a generic code voting protocol.
VeryVote do not offer any special protection against vote buying and coercion.
–
–
It suffer from the problems of traditional remote voting systems, e.g. postal voting.
The verification mechanisms of VeryVote do not break the voter’s privacy per se.
Although, the voter can collaborate with the attacker to produce a convincing vote receipt.
Questions?
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
17
technology
MarkPledge Vote/Receipt
Privacy Safeguard
from seed
MarkPledge Vote/Receipt
Candidates
Vote Encryption
VoteEnc | BitEnc
Vote Receipt
(OpenBitEnc)
Alice
E(v0)
BitEnc(0)
W3E
Bob
E(v1)
BitEnc(1)
JRF
Charles
E(v0)
BitEnc(0)
R59
Dino
E(v0)
BitEnc(0)
KMZ
Challenge = c
Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
VOTE-ID 2009, 7-8 September 2009
18