Shorter Lattice-based Zero-Knowledge Proofs for the Correctness of a Shuffle

Published in Financial Cryptography and Data Security Workshop VOTING’21, 2021

Recommended citation: Herranz J., Martínez R., Sánchez M. (2021) Shorter Lattice-Based Zero-Knowledge Proofs for the Correctness of a Shuffle. In: Bernhard M. et al. (eds) Financial Cryptography and Data Security. FC 2021 International Workshops. FC 2021. Lecture Notes in Computer Science, vol 12676. Springer, Berlin, Heidelberg

In an electronic voting procedure, mixing networks are used to ensure anonymity of the casted votes. Each node of the network re-encrypts the input list of ciphertexts and randomly permutes it in a process named shuffle, and must prove (in zero-knowledge) that the process was applied honestly. To maintain security of such a process in a post-quantum scenario, new proofs are based on different mathematical assumptions, such as lattice-based problems. Nonetheless, the best lattice-based protocols to ensure verifiable shuffling have linear communication complexity on $$N$$, the number of shuffled ciphertexts.

In this paper we propose the first sub-linear (on $$N$$) post-quantum zero-knowledge argument for the correctness of a shuffle, for which we have mainly used two ideas: arithmetic circuit satisfiability results from Baum et al. (CRYPTO’2018) and Beneš networks to model a permutation of $$N$$ elements. The achieved communication complexity of our protocol with respect to $$N$$ is $$\mathcal{O}(\sqrt{N}\log^{2}(N))$$, but we will also highlight its dependency on other important parameters of the underlying lattice ingredients.