Non-interactive shuffle arguments

Abstract

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).Ivoting 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.It is far from obvious how to achieve an equivalent result with encrypted digital ballots.Who should perform the mixing procedure?How to guarantee that it was performed correctly?Is it possible that no one can trace the ballots?This problem can be solved with a distributed system called a mix-network.The idea is to let each peer in the mix-network shuffle (permute and rerandomize) the ciphertexts.This makes it computationally hard to trace the input ciphertexts to the output ciphertexts given that at least one peer is honest.However, each peer should also give a proof that the shuffling was done correctly to avoid substitution attacks.The proof has to be hard to forge (sound) and should leak nothing but the truth of the statement (zero-knowledge).Such proofs are called zero-knowledge shuffle arguments, and in this thesis, we study their constructions.Importantly, we avoid the heuristic security model, used in many of the previous works, which (incorrectly) treats a cryptographic hash function as a truly random function.We show that it 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.This is achieved by combining several recent tools like quasi-adaptive zero-knowledge arguments and SNARKs.We implement it 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 common reference string (CRS).Secondly, we study how to reduce trust assumptions.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 the universal composability setting.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 get zero knowledge even if all the peers are malicious.Additionally, we simplify the argument construction and prove its security based on weaker assumptions.