Haechi: Simple Commitment-based Keyless In-person Verifiable Elections

The presentation introduces Haechi, a novel system for keyless, commitment-based, in-person verifiable elections, designed to enhance trust and efficiency compared to existing solutions. The motivation stems from widespread distrust in election results globally, underscoring the need for transparent and verifiable processes.

The Need for End-to-End Verifiable Elections

End-to-End (E2E) verifiable elections aim to provide tools for voters and the public to verify results. Key verifiability goals include:

• Cast as intended: Voters can confirm their vote is recorded honestly.
• Tallied as cast: The public can confirm all recorded ballots are correctly tallied.
• Ballot privacy: Ensures secrecy of individual votes, even against coercers or vote buyers.

The focus of Haechi is in-person voting, which remains the primary method globally and offers a more controlled environment for strong security guarantees compared to remote voting, despite potential compromises like device malware. The speaker notes that Haechi’s privacy assumptions regarding the voting device are no worse than traditional non-cryptographic voting.

Limitations of State-of-the-Art (ElectionGuard)

The presenter highlights several drawbacks of ElectionGuard, a prominent encryption-based E2E verifiable system:

• Large Election Record Size: ElectionGuard encrypts every selection (e.g., 10 encryptions for 10 candidates), leading to a record size linear in the number of candidates. This can easily exceed 100 gigabytes for large elections, making public verification cumbersome.
• Key Management Complexity: Encryption necessitates key management, which is operationally cumbersome and prone to error (e.g., a real-world incident where an election had to be rerun due to a lost private key).
• Lack of Post-Quantum Privacy: ElectionGuard relies on discrete logarithm assumptions, meaning ballots are not post-quantum private. A quantum adversary could harvest ballots now and decrypt them later.

Haechi’s Key Innovations: Commitment-Based and Keyless Design

Haechi addresses these limitations by leveraging cryptographic commitments instead of encryption:

• Keyless: Eliminates the need for complex key management.
• Post-Quantum Privacy: Achieved through perfectly hiding commitments.
• Reduced Election Record Size: By committing to all selections into a single commitment per ballot, Haechi drastically reduces the record size.
• Integrity and Justice: Named after a legendary Korean animal symbolizing these virtues.

Haechi’s System Mechanics

Haechi’s design revolves around Peterson vector commitments, which offer:

• Perfectly Hiding: An unbounded adversary cannot learn anything about the message from the commitment, providing post-quantum privacy.
• Computationally Binding: Impossible to open a single commitment to two different messages.
• Additively Homomorphic: Crucial for efficiently tallying votes (product of commitments equals commitment to sum of messages).

Ballot Creation and Verification Loop

1. Voter Selection: Voter makes selections, represented as a vector x (e.g., [0,0,1] for voting for the third candidate).
2. Device Commits: The device generates a ballot by committing to x using a Peterson vector commitment C and randomness sigma. It also generates a confirmation code (hash of C).
3. Voter Choice (Cast or Challenge):
   • Challenge: If the voter doubts the device’s honesty, they can challenge. The device reveals sigma. The voter (via their device) reconstructs the commitment C' using their original selections and sigma. If C' != C, the device was dishonest. This mechanism ensures cast-as-intended verifiability at the time of voting. Challenged ballots are spoiled and not counted.
   • Cast: If the voter accepts the ballot, the device adds C, associated proofs, and the confirmation code to the election record. The randomness sigma and selection x are added to a running tally. The voter leaves with their confirmation code.

Tallied-as-Cast Verifiability

After all votes, the device makes the final tally and election record public. The public can verify the tally using the additive homomorphic property:

• The product of all individual ballot commitments C should equal the commitment to the aggregate tally. Any discrepancy indicates a dishonest count.

Cast-as-Intended (Post-Voting) and Privacy

• Confirmation Code: Voters use their unique confirmation code to verify their ballot’s presence and integrity in the final election record. If their code is missing or does not match the hash of the commitment in the record, it signals tampering (deletion or alteration) of their ballot.
• Strong Ballot Privacy: The election record (commitments, zero-knowledge proofs, confirmation codes) reveals no information about individual votes. Crucially, even the voter cannot prove how they voted to a third party (e.g., a coercer) because they do not know the randomness sigma used for their cast ballot.

Ballot Well-Formedness Proofs

To prevent malicious voters or devices from casting invalid ballots (e.g., voting for multiple candidates when only one is allowed), Haechi includes a zero-knowledge proof of well-formedness. For traditional “choose one out of N” elections, this means proving:

1. Each selection x_i is either 0 or 1.
2. The sum of selections sum(x_i) is 1.

This is achieved by transforming the non-linear condition x_i * (1 - x_i) = 0 into linear equations using polynomial representation and the Schwartz-Zippel lemma, which are then proven using a non-interactive Sigma Protocol (via Fiat-Shamir heuristic). The proof consists of a group element and several scalars. Haechi offers both regular and compressed sigma protocols, with the choice depending on the relative size of group elements and scalars in the chosen cryptographic group.

Implementation and Evaluation

Haechi was benchmarked against ElectionGuard:

• Group Choice: Initially, Haechi used the same finite field group as ElectionGuard (496-bit group elements, 256-bit scalars), where regular sigma protocols were more efficient.
  • Record Size: For 100 candidates, ElectionGuard required 115 KB/voter, while Haechi required 7 KB/voter. This reduction is significant because ElectionGuard’s encryption size grows linearly with candidates, whereas Haechi’s commitment size is constant.
  • Performance: Haechi’s record generation was 3 times faster, and proof verification was 15 times faster than ElectionGuard.
• Elliptic Curve Groups: Further optimizations using elliptic curve groups (P256, P384) were explored, where group element and scalar sizes are comparable, making compressed sigma protocols more efficient.
  • For P256 with 100 candidates, Haechi’s record size dropped to 826 bytes/voter.
  • This translates to a massive reduction for large elections: 1 million voters and 100 candidates would require ~100 GB for ElectionGuard but only ~800 MB for Haechi.

Conclusion

Haechi provides a simple, commitment-based, keyless, and in-person verifiable election system that offers:

• Restored Confidence: Through E2E verifiability.
• Post-Quantum Privacy: Securing votes against future quantum threats.
• Practicality: Drastically reduced election record size and improved performance, making large-scale verifiable elections feasible.

• Tags:
• Cryptography
• Zero-Knowledge Proofs
• Post-Quantum Cryptography
• Verifiable Elections
• E2E Verifiable Voting
• Commitment Schemes
• Peterson Vector Commitments
• ElectionGuard
• In-Person Voting