reynolds

A method for electronic voting with Coercion-free receipt: 

A method for electronic voting with Coercion-free receipt David J. Reynolds (unaffiliated)

The central problem: 

The central problem How to get a DRE to properly encrypt a vote? How to ensure encrypted votes are properly tallied?

Some Stricter Requirements: 

Some Stricter Requirements End-to-end verifiable No ‘trust’ for integrity ‘Election authorities’ preserve privacy only ‘containment’ is distributed No one authority can expose a vote no trusted computational devices  Voter participates critically in verification

Expose fraud-in-collection using…: 

Chaum (optical) --- Neff --- This system --- Expose fraud-in-collection using… Temporal sequence Temporal sequence Human optical skills

How it works: 

How it works Analogy Model DRE = ‘Collector’ Collector has invisible-ink pen = public key invisible-ink writing = public-key encrypted Tallier has ‘magic-marker’ magic-marker = private key

Slide6: 

Meet with Collector Collector writes your vote using invisible-ink pen; you can’t read invisible ink You can write in ordinary-ink, must not reveal vote Bring your vote to bulletin-board Tallier (privately) uses magic-marker to read invisible ink on your vote Can the Tallier detect fraud by collector? YES!!!

(convention): 

(convention) Represents 625 in invisible ink (= encrypted in public key) Represents 625 in ordinary ink (= plaintext)

Filled ballot (preview): 

Filled ballot (preview)

Terminology: 

Terminology 'On' = voted for 'Off' = not voted for L options The ‘vote’ is the on-option The others are the off-options (K of L voting: K on-options, L-K off-options)

Polling process: 

Polling process Voter announces vote=green ‘Verification Phase 1’: voter fills external verification values for off-options collector enters vote; copies external v.-values for off-options to internal ‘Collector commit’: Writes randomly-chosen internal v.-value for on-option ‘Verification Phase 2’: voter fills external verification value for on-option

Verification process: 

Verification process Tallier checks that internal verification values equal external verification values for off-options That’s the method!! ‘Verification condition’

The heart of the method: 

The heart of the method During verification/tallying, a condition is checked for each off-option (of the vote as encrypted) The Collector can not* satisfy this condition for the on-option (of the true vote) (*P_success = 1/1000) That’s all we need!! MUST MEET TWO CRITERIA

Slide13: 

Fraud  on-option of true vote = off-option of vote-as-encrypted … a condition is checked for each off-option…. The Collector can not* satisfy this condition for the on-option (of the true vote) a) is ensured by the tallying/verification arrangement b) is ensured by the polling sequence and voter vigilance

Important feature: 

Important feature Voter just needs to Ensure that the temporal sequence is OK (‘commit’ phase occurs before voter enters v.value for on-option) That the v.value for on-option is as voter specified Voter does not need to check verification-values for off-options (Neff’s method has this feature too)

DRE & Coercion-properties: 

DRE andamp; Coercion-properties Use identical UI and front-end receipting system to Neff’s Requires printer with minimally-modified housing (commit must be seen to be made, but not readable) Fully coercion-free. Voter has full control over receipt outcome, regardless of vote.

Tallying methods: 

Tallying methods Re-encryption mix-net Chaumian mix-net Without mix-net (with homomorphic encryption)  Complexity linear in L (Independent of K)

Notation: 

Notation Layout in Analogy True DRE receipt Receipt is substantially: ID, ,

Homomorphic Tallying: 

Homomorphic Tallying . Encrypt vote as an L-tuple (‘unitary’) Encrypting the vote

Homomorphic tallying: 

Homomorphic tallying Proving the vote DRE proves for each k in 1..L in Zero-knowledge OR OR a. Verification condition To prove 1-of-L (not double-voted on issues) Prove that the product of all encrypts 1  simply reveal the randomizer of the product b. Proving the vote 1-valued DRE proves for each k This proving-1-valued is linear in L (long known method for ‘unitary’ approach)

Homomorphic tallying: 

Homomorphic tallying Counting the vote Trivially linear because of encrypting as L-tuple; all of the votes on options are encrypted separately  Take the product of encrypted votes on each option (through votes of all voters) and Talliers decrypt result = total number of votes on that option

Adapting other methods to achieve homomorphic tallying, linear in L : 

Adapting other methods to achieve homomorphic tallying, linear in L Assume DRE has already verifiably encrypted the vote Assume we can construct reasonable ZKP’s of above form DRE encrypts vote again as L-tuple (unitary) as specified Prove that the in the linear fashion shown above DRE proves that encrypts same vote as provides ZKP for each option k of the vote that OR

Re-encryption Mix-net Tallying: 

Re-encryption Mix-net Tallying . Just need re-encrypt property Encrypting the vote

Re-encrypt. mix-net tallying: 

Re-encrypt. mix-net tallying Proving the vote DRE proves for each k in 1..L in Zero-knowledge OR a. Verification condition Can now go into mix-net

Re-encryption mix-variant: 

Re-encryption mix-variant Leverage assumed homomorphic property to ‘subtract’ external from internal verifiers while they remain encrypted Results must travel with vote in mix-net Spares ZKPs from DRE, adds complexity to mix-net May be possible to reduce complexity by packing more than one number into 1 (familiar techniques) (d_overall = d_1 + 1000 d_2 + 1000.1000 d_3)

Chaumian Mix-net Tallying: 

Chaumian Mix-net Tallying Encrypting the vote Input-batch element: Output-batch element: Verification condition (on output element):

DRE-Calculating ahead: 

DRE-Calculating ahead DRE can keep cache of calculations Assume voter often takes default verification-values for off-options ZKPs only need be calculated for on-option while voter waits Re-fill cache in separate thread

Conclusions: 

Conclusions Coercion-free verifiable system, very good security properties (p_detection=1/M ) Tally with re-encryption/Chaumian mix-net or homomorphic encryption Homomorphic tallying linear in L

More material: 

More material Search for ‘Reynolds’ on iacr’s eprint website www.iacr.org (Should be accepted soon!)