Study Group: Proving Correctness of a Shuffle

Today David and Essam talked about shuffle proofs. These allow to prove that a shuffle and re-randomisation of a list of ciphertexts was done correctly. The main application is e-voting, where several hosts in a so-called mix net sequentially shuffle and re-randomise ciphertexts containing the votes. Shuffle proofs ensure that no host can tamper with the votes. As usual, the requirements for shuffle proofs are completeness, soundness, and zero-knowledge. Most proofs are based on (semi-)homomorphic cryptosystems such as ElGamal that allow to re-randomise a ciphertext without knowing the cleartext.

In the last millennium, Sako and Kilian presented a cut-and-choose implementation of shuffle proofs: The prover shuffles the input ciphertext list X once more to get Z, and the verifier ask to see either the randomness used, or the randomness that would be used to shuffle X to Z. The correct response to both queries allows to compute the randomness for shuffling X to Y, which reveals a cheating prover with probability 1/2. Zero-knowledge follows from the fact that both replies on their own are independent on randomness used to shuffle X to Y.

More recently, Wikström presented a more efficient solution using extended Pedersen commitments, Schnorr-like protocols, and batch proof techniques. Extended Pedersen commitments allow to commit to a vector in only one group element. The protocol works in two phases. In an offline phase, the prover commits to a random permutation as a matrix and proves it be correct. Later, the provers shuffles the input ciphertext list according to the committed permutation and proves having done so.

At Eurocrypt 2012, Bayer and Groth presented another solution combining similar techniques, Groth's earlier work on sublinear size arguments and algebraic techniques like FFT and the Schwartz-Zippel lemma. An implementation of their protocol can prove the correctness of a shuffle of 100'000 ciphertext in 2 minutes.