Belenios: a system for secret voting

As part of the recent discussion on switching to secret voting for Debian general resolutions (GRs), which has resulted in a ongoing GR of its own, the subject of voting systems that embody various attributes some would like to see for voting in Debian has been brought up. One of the systems mentioned, Belenios, provides an open-source "verifiable online voting system". Whether or not Debian chooses to switch to secret voting, Belenios would seem to provide what other projects or organizations may be looking for as a mechanism to handle their voting needs.

Background

As highlighted by the discussion of, and amendments to, the Debian GR, secret voting means different things to different people. Generally, though, people want trustworthy elections foremost, which means that voters (and those affected) need to understand and believe in the mechanisms used to cast their ballots and tabulate the results. There are cryptographic protocols that can be used to provide a technical solution to some or all of those problems, but there are social and other considerations that may render them unusable in real elections—at least those held by governments at various levels. Our coverage of a talk at linux.conf.au 2020 can help with some of the reasons for that, along with accounts of poorly written implementations of the cryptographic protocols for voting systems.

Debian currently has two types of votes: an annual election for the Debian project leader (DPL)—this year's DPL election process started on March 5—and for GRs that get the requisite support from Debian developers (DDs). Six developers can force a vote on any issue via a GR, one sponsor and five seconds is all that it takes. All of the voting is done via PGP-signed email and the ballots and voter lists are published for all to see after the vote. The difference is that DPL election results do not provide a mapping from voter to ballot, while GR voters and ballots are matched up, so everyone can see how each voter chose to rank the options on the ballot.

Debian uses the Condorcet voting system, which allows voters to rank their choices of candidates or proposals, with some specific mechanisms for dealing with the relatively unlikely circular results that can arise at times. It is, already, a fairly complicated scheme that requires some sophisticated thinking from voters in order to understand how it works. Various other forms of ranked voting have been used in governmental (and other) elections to try to avoid some of those complexities for elections with a less-technical electorate.

For both Debian election types, anyone can use the published ballots to verify that the reported results match the votes cast; any DD can also directly see that their recorded vote matches how they voted for GR elections. For DPL elections, the devotee vote-collecting system returns a secret code to voters when a correctly signed ballot is submitted via email; that code can be used with the hash value reported in the tally sheet to verify that their vote was included in the ballots. In both cases, developers who did not vote can check to ensure that no vote was recorded for them, either by checking the separate voter list for DPL elections or on the tally sheet for a resolution. All of that adds up to a level of transparency for Debian voting.

Meanwhile, some voters have been uncomfortable with having their ballots published along with their names for GRs, especially contentious resolutions such as the 2021 GR about a position statement on Richard Stallman's return to the FSF board. That led to the current resolution, which is meant to change resolution voting to be reported the same way as DPL elections are now, breaking the link between voters and their ballots.

One of the other pieces of the original secret-voting proposal (there are currently two other ballot options that will be voted on as part of the GR) is to remove the requirement of voting by email from the Debian Constitution. That would allow the project secretary to explore alternative voting mechanisms that might augment the current email-based system; some developers are worried that might also lead to eliminating the ability to vote by email, however. Longtime secretary Kurt Roeckx plans to look into Belenios if the email-voting requirement is removed.

Belenios

The Belenios system would seem to provide much of what the proponents of secret voting on GRs are looking for. It is developed by Stéphane Glondu, who is a Debian developer, and provides both vote privacy and verifiability using homomorphic encryption. Using that mechanism, no one can actually see the ballot of any particular voter; the outcome can be calculated without decrypting the ballot. The home page describes the verifiability of the systems as follows:

Every voter can check that her vote has been counted and only eligible voters may vote. [Verifiability] relies on the fact that the ballot box is public (voters can check that their ballots have been received) and on the fact that the tally is publicly verifiable (anyone can recount the votes). Moreover, ballots are signed by the voter credential (only eligible voters are able [to] vote).

The "how it works" page gives more detail on the process and the Belenios paper goes into even further detail. Voters have a set of login credentials for the web interface (username/password) as well as a separately communicated credential that is the private ElGamal key for the user. The server stores the associated public key; the voter makes their choices, then the private key is used client-side to encrypt the ballot, which is sent to the server.

The server uses the public key to validate the ballot, using a zero-knowledge proof supplied by the client that the ballot is valid (e.g. only contains votes for the proper number of options). A zero-knowledge proof is a way to prove an assertion without giving any additional knowledge to the entity who is verifying the proof, other than that the assertion is true. In this case, the validity of the ballot can be proved without giving the server any information about the actual vote choices in the ballot. The linked-to Wikipedia entry has some "real world" examples, along with the mathematical background for the idea of a zero-knowledge proof.

Once the server has validated the ballot, it then lists the "tracking number" (a hash of the encrypted ballot) for the ballot on the public information page for the election. Voters can check for their tracking number on that page and, using their private key locally, can see their actual vote recorded on the ballot; no one else can decrypt the ballot itself. The key pair is normally generated by the server and the private half is discarded after sending it to the user, but it is possible for another entity to generate the keys and communicate each half to its respective owner. Securely distributing the private key is clearly an important aspect; unencrypted email may not be the best choice.

The outcome of the election is determined by the tally process, which is described this way:

By default, the election server stores the decryption key. The encryption scheme has a particular property, called a homomorphism: from the encrypted ballots, anyone can compute the encryption of the result (the sum of the votes for each candidate) by combining the ciphertexts (without using any key). This way, only the final encrypted result needs to be decrypted, which guarantees vote privacy: the ballot of an individual voter is never decrypted.

The final encrypted result of the election can instead be decrypted by one or more election administrators who have been designated as decryption authorities; all of those authorities need to collaborate to decrypt the result. Another zero-knowledge proof is used to show that the encrypted outcome of the election is the result of the votes made, once again without decrypting the ballots. To a certain extent, it sounds like "magic cryptographic fairy dust", but the underlying principles are well-established and well-understood—at least within the cryptographic world.

Tools for auditing and verifying the process are part of the Belenios repository, though the project welcomes others to create tools for working with the system. The protocol specification "should provide all the necessary details (but of course, questions are welcome)". The online Belenios server can be used to run elections of up to 2500 voters, or, of course, the code can be run elsewhere on a private server. The FAQ has information on doing so (as well as answers on other topics). One thing that does not seem to be mentioned on the site is whether there has been any security audit or formal verification of the Belenios code; one suspects that may need to happen before it can be adopted, at least for some kinds of votes.

The default mechanism for running the vote is a form of approval voting where voters can choose one or more of the candidates they find acceptable; "for example, she can select between 3 and 5 candidates among a list of 10 candidates". Support for other voting mechanisms (including Condorcet voting) is under development.

Back to Debian

The plan to remove the "by email" phrase from the constitution, which is part of the original proposal by Sam Hartman (Proposal A on the GR page) is one that does not sit well with some, even if they are inclined toward moving to secret ballots. That has resulted in Proposal B, which only adopts the secret-voting language, leaving "email" alone and not adding the two provisions about overriding or replacing the secretary that are part of Proposal A. There is also Proposal C that would re-affirm public voting for resolutions, which was added, at least in part, because the implementation details of a secret-voting system are not specified in the other proposals.

It seems at least plausible that an email vote-collection mechanism could be added to Belenios if Proposal B carries the day. It could use Debian developers' public PGP keys on the distribution keyring to encrypt the ElGamal private key needed to create a properly signed ballot; those could be sent to each developer. Or, potentially, Belenios could be changed to use emails signed with developers' PGP keys directly. That might open up the ability for some voters to use the Belenios web application and others to use email as usual. Obviously, if Proposal C is the winner, none of that will be needed.

There are some known weaknesses in the system used for DPL elections; users could be forced to reveal their secret code, or a group of users could collaborate to unmask their votes, either of which would break the secrecy of the ballots. Those problems are not really alleviated with Belenios, as the ElGamal private key plays the same role as the devotee secret code, but the distribution has been living with those possible attacks for a long time now.

The discussion period on the secret-voting resolution runs until March 11, so other proposals could be added to the ballot before then. The two-week voting period will presumably start shortly thereafter. It seems at least possible, perhaps even likely, that Proposal A went a bit too far in terms of trying to clean up somewhat unrelated ambiguities (secretary overreach); in addition, eliminating the email language may also be a step too far for some. There would seem to be legitimate reasons to move away from public voting on GRs, even if the most contentious ones tend to be political, rather than technical or Debian-internal, questions that many DDs think shouldn't be voted on at all. In any case, we should know what the project thinks about secret voting by the end of March or so. If secret voting is chosen in some form, perhaps Belenios can be adapted to fit the bill.