What is a Zero-Knowledge Proof?
Verifying a secret’s truthfulness without revealing the secret itself
Have you ever tried to demonstrate to another person that you know a secret without revealing the secret itself? It might seem difficult to convince them that you have specific knowledge without telling them what that knowledge is. However, this is the exact scenario for many digital and online processes in which the system must verify that certain information is correct or true without disclosing the potentially sensitive content (such as personal data). This is precisely where zero-knowledge proofs (ZKPs) come in.
A ZKP is a cryptographic protocol between a prover, who we can call Peggy, and a verifier, Victor, in which the former tries to convince the latter that some statement is true without revealing any information other than the truthfulness of the statement. The theory behind ZKPs is explained rather well in the article How to explain zero-knowledge protocols to your children.
The story tells of a magic cave whose entryway forks into two dark winding passages: one to the left and the other to the right. Apparently, deeper into the cave, the two paths migrate back toward one another and almost connect to form a continuous, circuitous path, but remain separated by a wall. Therefore, if you decide to run into one passage, you must get out of the cave by turning around and taking the same passage back.
Nevertheless, the cave holds a secret: whispering the magic words “open sesame,” the wall between the passages opens and they become connected. Peggy tells Victor that she knows the magic words that open the wall, but he wants her to demonstrate that this is indeed true. In order to do so, Victor proposes a challenge: he will wait at the entry of the cave and will ask Peggy to go into the cave using the left-hand passage and to come out using the right-hand passage. This is only possible if Peggy knows the magic words, so if she successfully completes the challenge, Victor can be convinced that Peggy knows the magic words despite neither of them telling the other what the magic words are.
In this way, a zero-knowledge proof should satisfy the following properties:
- Completeness: If the statement is true, the prover can succeed in convincing the verifier that it is true.
- Soundness: If the statement is false, a prover cannot succeed in convincing the verifier that it is true.
- Zero-knowledge: If the statement is true, a verify does not learn anything more about the statement other than that it is true.
How are zero-knowledge proofs used in online voting systems?
Zero-knowledge proofs are a key element when talking about verifiability or vote correctness in online voting systems (to learn more about security requirements for online voting, check out this article).
Vote correctness
Let’s think of a referendum in which the voter is presented with a list of questions, and they have to answer either yes or no to each one of them. In order to encrypt these answers, the voting device (a mobile phone, a laptop, etc.) understands the answer yes as a 1 and the answer no as a 0. In this kind of system, it is important to demonstrate that the value encrypted is indeed a 1 or a 0, in order to prevent a malicious voting device from voting more than once for a question, e.g.: encrypting a choice with the number 3, giving 3 yes votes to a single question. In order to do that, the system generates a zero-knowledge proof to prove that the value encrypted is either a 1 or a 0 without giving any clue about the exact choice that was encrypted.
Universal verifiability
In order to provide universal verifiability, an online voting system should generate evidence which enables anybody to check that the election results have been calculated from votes cast by eligible voters, and that these votes have not been manipulated during the counting process. This evidence is usually provided in zero-knowledge proofs.
Independently of the anonymization mechanism used during the counting process (such as mixing or homomorphic tallying), votes must be decrypted. Decryption is a sensitive operation that needs a private key to be executed. This key must be protected in order to preserve each voter’s privacy. If we want to verify that the decryption process has been done correctly and that no votes have been modified, added, or deleted during the process, zero-knowledge proofs are generated in order to demonstrate that the decrypted votes are those that were encrypted, without leaking any information about the election private key and the contents of each vote.
Zero-knowledge proofs are just one of the many security protocols that can be implemented in an election with online voting, and they specifically help to offer verifiability and a certain level of transparency while still protecting voter privacy and overall election integrity. If you’re interested in taking a deep dive into ZKPs and other security mechanisms and processes used for online voting, take a look at our resource center.
This article was written by Núria Costa, Cryptography Researcher at Scytl
