On Friday, August 28 Janno Siim defended his PhD thesis „Non-Interactive Shuffle Arguments„
A fundamental requirement for all democratic governments is a secure voting system. In recent years some countries, like Estonia and Switzerland, have adopted internet voting (i-voting), and many more have experimented (e.g., Norway and Australia) or have plans to adopt it in the future (e.g., Lithuania and Russia). I-voting has the potential to offer better convenience, lower administrative costs, and higher voter turnout, but this comes with increased security concerns and significant technical challenges.
Consider the simple procedure of shaking the ballot box to mix the order of the ballots. Mixing is essential to anonymize voters, but it is far from obvious how to achieve an equivalent result with encrypted digital ballots. Who should perform the mixing procedure? How to make sure that votes are not removed or substituted? Can we be sure that votes cannot be traced?
We can solve this problem with a distributed system called a mix-network. The idea is to let each peer in the mix-network shuffle (randomly reorder and obfuscate) the ciphertexts. This will make it computationally overwhelming to trace the input ciphertexts to the output ciphertexts assuming that at least one peer in the mix-network is honest. However, each peer should also prove that it performed the shuffle correctly to avoid substitution attacks. The proof has to be hard to forge (sound) and should leak no information besides the truth of the statement (zero-knowledge). Such proofs are called zero-knowledge shuffle arguments, and this thesis studies their constructions. Importantly, we avoid the heuristic security model, used in many previous works, which (incorrectly) treats a cryptographic hash function as a truly random function. We show that it is possible to construct shuffle arguments, that are efficient enough for large-scale elections, in other security models than the random oracle model.
First, we construct a very efficient non-interactive shuffle argument that avoids the random oracle model and instead uses the generic group model. We achieve this by combining several recent tools like quasi-adaptive zero-knowledge arguments and SNARKs. We implement our argument and observe practical efficiency for large-scale elections: the proving time for 100,000 ciphertexts is less than a minute, and verification time is less than 1.5 minutes on modest hardware. Unfortunately, security requires that the prover and the verifier have access to a trusted reference string (CRS).
Secondly, motivated by the previous issue, we study how to reduce trust assumptions in zero-knowledge arguments. There are efficient multiparty computation (MPC) protocols for generating CRSs for a large class of arguments, but they require the random oracle model. We improve upon one such protocol and, among other results, remove the requirement for the random oracle. We prove the security of this protocol in a framework that allows composability with different protocols.
Thirdly, we modify our shuffle argument to be applicable to the above MPC protocol. This guarantees both soundness and zero-knowledge as long as at least one peer in the MPC protocol is honest. We go one step further and show how to obtain zero-knowledge, even if all the peers are malicious. Additionally, we simplify the argument’s construction and prove its security based on weaker security assumptions.
