INNOVATE
How to Avoid Repetitions in Lattice-Based Deniable Zero-Knowledge Proofs
Making Deniability User-Friendly
Privacy, integrity and verifiability are some of the basic security requirements an electronic voting system should satisfy in order to meet the security needs of real elections. Nevertheless, there are other requirements which are also desirable, such as deniability, also known as non-transferability. Informally, deniability means that the person who interacted with the system can later deny the result of the interaction, even if the system outputs some proof of their interaction.
For example, in electronic voting, we use cast-as-intended proofs to show that the encrypted ballot undoubtedly contains the voter’s intended choices, and not something else. However, if such a proof can also convince another person that a voter’s ballot contains certain choices, it would possibly enable vote-selling and voter coercion. Therefore, no one except the voter must be able to verify the ballot correctness proof. In other words, ballot correctness proofs should be non-transferable.
These proofs, commonly known as deniable proofs, are interactive zero-knowledge proofs. This interaction consists of a number of rounds in which the voter and the system exchange messages. Naturally, we cannot have a deniable proof without making extra assumptions unless there are at least three rounds of interaction between the person and the system. One-round solutions are insufficient, while all known two-round protocols require additional assumptions to be made, like a random oracle, a common reference string, a public key infrastructure, etc. Fortunately, we know how to obtain efficient deniable proofs with three rounds of interaction using classical cryptography.
Many security experts believe that soon quantum computers will become mature enough to break the existing cryptography. Unfortunately, all interactive zero-knowledge proofs in classical settings are not quantum-secure. Therefore, we should look for solutions that can withstand such threats. One of the most promising cryptographic approaches for achieving security in front of quantum computers is lattice-based cryptography.
Luckily, there exist many efficient lattice-based interactive zero-knowledge proofs. However, they work a bit differently than their classical counterparts. For example, to prevent a secret from being leaked, most of the efficient lattice-based interactive schemes must employ a technique called “rejection sampling”. This means that the interaction does not always output a proof during the first execution; instead, it might choose to abort and return nothing. Aborting or terminating depends on a complex mathematical rule. If the result does not meet the condition, the whole proving process must be re-run until it does. Theoretically, we may need to repeat the interaction many times before getting the desired proof.
While repetitions are acceptable in many cases, we want to avoid re-runs for usability reasons in some practical applications. For example, we do not expect voters to ask their voting device for a cast-as-intended proof over and over again. We might also imagine a malicious voting device that deliberately aborts the process in hopes that the voter will get tired and leave without receiving a ballot correctness proof.
In our article, presented at the 2022 NordSec Conference on December 2, we show a generic technique that makes it possible to obtain a three-move zero-knowledge system without re-runs from any multiple-round zero-knowledge system that might require re-runs. The transformation combines the well-known Fiat-Shamir technique for obtaining a non-interactive proof with a couple of initially exchanged messages. The resulting three-move system takes advantage of honest-verifier zero-knowledge and can be easily turned into a fully deniable proof using standard methods.
We admit that not all use cases are sensitive to aborts. For example, it seems our construction is not beneficial for blind signatures. However, user identification, deniable signatures, and cast-as-intended verification might all benefit from our solution.
Finally, our implementation shows that adding the transformation increases execution time by only roughly 5%. Additionally, a battery of 10,000 tests for the non-transformed protocol demonstrates that more than 6% of the executions need ten repetitions or more of the protocol. Given all of that, we believe that our construction is practical and beneficial in cases when repetitions are not desirable.
