Project type: Bridge Project

Privacy-Preserving and Software-Independent Voting Protocols

Here are five considerations that explain the unmet needs of this proposed project.

  1. Voting protocols, both in form of Voting Governance Protocols and Internet Voting Protocols have become increasingly popular and will be more widely deployed, as a result of an ongoing digitalization effort of democratic processes and also driven by the current pandemic.
  2. Elections are based on trust, which means that election systems ideally should be based on algorithms and data structures that are already trusted. Blockchains provide such a technology. They provide a trusted bulletin board, which can be used as part of voting.
  3. Voting crucially depends on establishing the identity of the voter to avoid fraud and to establish eligibility veri ability.
  4. Any implementation created by a programmer, be it a Voting Governance Protocol or an Internet Voting Protocol can have bugs that quickly erode public confidence. Proof assistants are established tools that help to avoid large classes of common programming mistakes.
  5. Greenland laws were recently changed to allow for Internet Voting.

Having said all of this, tackling these unmet needs is a real research challenge. Decades of research in voting protocols have shown how diffcult it is to combine the privacy of the vote with the auditability of the election outcome. It is easy to achieve one without the other, but hard to combine both into one protocol. Thus, the topic of this proposed research proposal is to study voting protocols that are privacy-preserving and software-independent in the sense of Rivest and Wack’s definition. “A voting system is software-independent if an undetected change or error in its software cannot cause an undetectable change or error in an election outcome.” No such protocol is known to exist for online voting. In future work, we expect to apply the knowledge gained of this proposed research project more broadly to other security protocols.

The proposed research project aims to shed more light on the overall research question, if and what role blockchain technologies should play in the design of software-independent Voting Governance Protocols and Internet Voting Protocols in theory and practice. Affirming this research question in the positive would lead to a new generation of voting protocols that derive trust in the election outcome from trust in the blockchain, they would increase public con dence in the proper treatment of voter eligibility, and they would deliver technology for post-conflict and developing countries, where the population has little trust in paper evidence. This would trigger further innovation in the Voting Governance Protocol and Internet Voting markets. To answer this research question, we structure the research into two research objectives, which we elaborate on next.

  • (RO1) Explore the notion of software-independence, verifiability, and accountability in the context of blockchain voting protocols.
  • (RO2) Mapping the concept of vote privacy to the privacy-preservation in blockchains and how to scale this to a formally-verified and software-independent voting protocol.

Research methodology. In order to achieve (RO1), we will consider two theories of what constitutes software-independence. There is the game-theoretic view, which, similar to proof by reduction and simulation in cryptography, reduces software-independence of one protocol to another. The genesis protocol that was originally advocated by Rivest bases trust entirely on paper evidence, but there are alternatives, based on digital evidence, testing, and statistics. We plan to understand what software-independence actually means for blockchain voting protocols. We plan to consider these formal models of software-independence that we plan to study using proof assistants, to give even stronger software-independence guarantees. For all voting protocols that we design within this project, we will develop formal proofs of software independence, verifiability, and accountability.

To achieve (RO2), we start from the assumption that the blockchain provides sufficient privacy guarantees. We piggy-bag on blockchains that have a clear formal definition of what is meant by privacy, and that are mechanically proven correct. Based on results, we will then reconsider the designs of existing voting protocols, and design new voting protocols by choose-pick the best elements with the goal to achieve a software-independent protocol. A formal de nition of software-independence and a mechanized proof of correctness will be done in this work-package. Time permitting, we will extend our notion of software independence to other guarantees, including receipt freeness, coercion mitigation, and dispute resolution.

For a secure implementation, one needs to make sure that the deployed code correctly implements the protocol. We aim to automatically extract an executable verified smart contract from the formal model developed. The Concordium blockchain provides a secure and private way to put credentials, such as passport information, on the internet. We will investigate how to reuse such blockchain based identities for voting. Based on the results, we propose to develop an open-source library that makes our verified blockchain voting technology available for use in third-party products. We envision to release a product similar to Election Guard (which is provided by Microsoft), but with a blockchain functioning as a public bulletin board.

Scientific value
Internet voting provides a unique collection of challenges, such as, for example, vote privacy, software independence, receipt freeness, coercion resistance, and dispute resolution. Subsets of them can be solved separately, here we aim to guarantee vote privacy and software independence by the means of a privacy-preserving and accountable blockchain and formally verify the resulting voting protocol. The resulting voting protocol will be di erent from the existing ones, because they build on formally verified properties that are guaranteed by the choice of blockchain.

Capacity building
The proposed project pursues two kinds of capacity building. First, by training the PhD student and university students affiliated with the project, making Denmark a leading place for secure Internet voting. Second, if successful, the results of the project will contribute to the Greenland voting project and to international capacity building in the sense that they will strengthen democratic institutions.

Business value
The project is highly interesting to and relevant for the industry. There are two reasons why it is interesting for Concordium. On the one hand voting is an excellent application demonstrating the vision of the blockchain, and on the other hand Concordium will as part of the project implement a voting scheme to be used for decentralized governance of the blockchain. More precisely, the Concordium blockchain is designed to support applications where users can act privately while maintaining accountability and meeting regulatory requirements. Furthermore, it is an explicit goal of Concordium to support formally verified smart contracts. Obviously all these goals fit nicely with the proposed project, and it will be important for Concordium to demonstrate that the blockchain actually supports the secure voting schemes developed in the project. With respect to governance, Concordium has a need to develop a strong voting scheme allowing members of our community to vote on proposed features and to elect members of the Governance Committee. The project is of great interest to the Alexandra Institute to apply and improve in-house capacity for implementing cryptographic algorithms. The involvement of Alexandra will guarantee that the theoretical findings of the proposed project will we translated into usable real world products and disseminated further to Internet Voting providers that may eventually provide a voting solution to Greenland.

Societal value
Some nations are rethinking their respective electoral processes and they ways they hold elections. Since the start of the pandemic, approximately a third of all nations scheduled to hold a national election, have postponed them. It is therefore not surprising that countries are exploring Internet Voting as an additional voting channel. The result of this project would contribute to making Internet election more credible, and therefore strengthen developing and post-conflict democracies around the world. The election commission in Greenland, a partner in this proposed project, is currently actively pursuing the development and deployment of an Internet Voting system.

January 1, 2023 – December 31, 2025 – 3 years.

Total budget DKK 12,09 million / DIREC investment DKK 3,6 million

Participants

Project Manager

Carsten Schürmann

Professor

IT University of Copenhagen
Department of Computer Science

E: carsten@itu.dk

Bas Spitters

Associate Professor

Aarhus University
Department of Computer Science

Gert Læssøe Mikkelsen

Head of Security Lab

The Alexandra Institute

Kåre Kjelstrøm

Chief Technology Officer

Concordium ApS

Klaus Georg Hansen

Head of Division

Government of Greenland

Bernardo David

Associate Professor

IT University of Copenhagen

Diego Aranha

Associate Professor

Aarhus University
Department of Computer Science

Tore Kasper Frederiksen

Senior Cryptography Engineer

The Alexandra Institute

Ron Rivest

Professor

MIT

Philip Stark

Professor

University of California, Berkeley

Peter Ryan

Professor, Dr.

University of Luxembourg

Partners