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 https://doi.org/10.1007/978-3-662-63958-0_27
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.