DEP 16: Improved confidential voting for General Resolutions

Title: Improved confidential voting for General Resolutions
DEP: 16
State: DRAFT
Date: 2021-04-16
Drivers: Timo Röhling <timo@gaussglocke.de>
URL: http://dep.debian.net/deps/dep16
Source: https://salsa.debian.org/dep-team/deps/-/blob/master/web/deps/dep16.mdwn
License:
 Copying and distribution of this file, with or without modification,
 are permitted in any medium without royalty provided the copyright
 notice and this notice are preserved.
Abstract:
 An enhancement of the current voting scheme that allows verifiable
 voting results without the need to disclose individual voter
 preferences.

Introduction

This is a proposal to improve the way in which the results of confidential votes on General Resolutions are published.

In Debian, the voting procedure is administrated by the Project Secretary. The Secretary receives the votes from all voters, tabulates the results and publishes them. For public votes, the publication of voter identity and corresponding ballot provides accountability, as every voter can verify that

their ballot is correctly recorded in the results and
only legitimate voters have contributed to the results.

This protocol provides the same assurances for confidential votes.

Synopsis

In the current confidential voting scheme, the results are blinded by replacing each voter identity with a random pseudonym. Each voter is told their own pseudonym but none of the others. This enables each voter to confirm their own ballot, but nothing else.

The proposed verification for the pseudonyms is based on the Chaum-Fiat-Naor protocol for blinded checks: the Secretary creates N independent bijective mappings, i.e. each voter is assigned a unique pseudonym and every pseudonym belongs to an actual voter. After the vote, the Secretary is asked to reveal all mappings but one to prove that they followed protocol. If all N-1 mappings are bijective, the voters can be reasonably sure that the final mapping is also bijective, as long as the Secretary cannot know in advance which mapping will remain blinded.

The number N must be at least two. Increasing N strengthens the proof but also increases the required work for each voter.

Cryptographic Primitives

The protocol relies on a HMAC function HMAC(K, U) that computes an authenticated hash value from a secret key K and a user identifier U. HMAC functions are indistinguishable from pseudo-random functions unless the key K is known, which makes them convenient for the required random bijective mappings. There is an extremely small chance of hash collisions if the chosen key K is very unlucky, but the set of eligible voters is known in advance, so this can be checked and a different key be chosen.

Protocol

Preparation

Before the vote begins, the Secretary generates N different HMAC keys, K_1, K_2, ..., K_N and keeps them secret.

Voting

For each recorded ballot, the Secretary generates N verification tokens by applying the HMAC function keyed with K_i to the Debian User ID of the voter:

T_1 = repr(HMAC(K_1, U))
T_2 = repr(HMAC(K_2, U))
...
T_N = repr(HMAC(K_N, U))

The repr function converts the hash digest into an ASCII-friendly token of sufficient length.

The tokens are labeled with the Key ID and sent to the voter as part of their confirmation mail, e.g.

Token 1: 37k7s-e42qi-ahlx3-j26ev-afjwb
Token 2: jt6du-gar7z-ak7ja-bwjpp-p6qdp
...

Publication

At the end of the voting period, the DPL or another designated person randomly selects one of the N Key IDs whose tokens shall serve as Ballot Tokens. The choice must be announced publicly. The tokens which were created from the other Key IDs are designated Identity Tokens.

The Secretary then publishes

each voter identity with the corresponding N-1 Identity Tokens ("Identity List")
the N-1 HMAC keys which were used to generate the Identity Tokens
each recorded ballot with the corresponding Ballot Token ("Ballot List")

The Ballot List must be sorted lexicographically by token. This ensures that the position of a token in the Ballot List provides no information about the corresponding Identity Tokens. As a side effect, it also makes it easier to look up and verify tokens.

The Identity List should be sorted by voter identity, to enable easy side-by-side comparison with the list of legitimate voters.

The HMAC key for the Ballot Token must remain secret to ensure vote confidentiality.

Verification

In order to determine that the vote has not been tampered with, everyone should verify that

all tokens are unique,
the Identity List has only legitimate voters,
each Identity Token has been generated from the corresponding Debian User ID with the correct HMAC key, and
the Ballot List has the same length as the Identity List.

Additionally, every voter should verify for themself that

their Identity Tokens and their Ballot Token appear on the correct lists,
all their Identity Tokens actually refer to their identity, and
their Ballot Token refers to the correct ballot.

Rationale

This section outlines possible attacks against the protocol and how they are mitigated. Most attacks require the collusion of a malicious Secretary. This is a consequence of the role the Secretary has in the voting procedure and shall not be construed as mistrust against present or past secretaries who have fulfilled their duty with utmost reliability.

Attacks on the Confidentiality of the Vote

Using independent HMAC keys for the Identity Tokens and the Ballot Tokens guarantees that the token lists are uncorrelated for anyone who is not in possession of the keys. An attacker who seeks to breach confidentiality must either invert the HMAC function for the Ballot Tokens, or somehow obtain the HMAC key.

A malicious Secretary can leak individual voting behavior. This is very difficult to prevent without weakening the integrity guarantees.

Attacks on the Integrity of the Vote

A malicious Secretary could try to commit fraud by falsifying legitimate votes. This is mitigated by publishing each ballot with a token that enables the voter to verify correctness.

A malicious Secretary could vote on behalf of eligible voters who did not participate in the vote for some reason. This may not be immediately obvious and is only detectable because the list of purported voters becomes part of the public record. The public voting scheme is susceptible to the same attack.

A malicious Secretary could try to fabricate votes in addition to the legitimate votes. This is mitigated because it would either make the Ballot List longer than the Identity List, or the Ballot Tokens of some voters would have to be omitted in the hope that those voters do not verify their tokens.

In a more sophisticated attack, a malicious Secretary could try to assign the same Ballot Token to multiple users who voted identically. Those voters would unknowingly share and verify the same ballot; the mapping from voter identities to ballots is no longer bijective, which creates room in the Ballot List for fake votes. However, the Secretary is forced to create bijective mappings for the Identity List verification step to succeed. Therefore, this attack requires the attacker to guess in advance which token will become the Ballot Token, giving a one in N chance to evade detection.

Variations

The decision which token becomes the Ballot Token can be based on a pre-determined, public source of randomness, such as the low order bits of the hash of the first Bitcoin block that is mined after the voting period ends. This precludes collusion between the Secretary and the person who is responsible for selecting the Ballot Token.

Implementation Details

The proposed HMAC function is HMAC-SHA256 with a key size of at least 128 bits. The proposed digest representation function repr is a lower-cased RFC 4648 Base32 encoding, truncated to the first 25 characters and dash-separated into groups of five. The representation is chosen for its good readability, as most voters are going to verify their personal tokens manually.