Paper 2021/488

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

Javier Herranz, Ramiro Martínez, and Manuel Sánchez


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 \textit{et al.} (CRYPTO'2018) and Bene$\check{\text{s}}$ 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.

Note: @ICFA. The final version will be published by Lecture Notes in Computer Science, as the proceedings of Financial Cryptography Workshops 2021 (the results were presented at workshop VOTING'2021)

Available format(s)
Publication info
Published elsewhere. Minor revision. to be published in the Proceedings of VOTING'2021 (Financial Cryptography Workshops). The copyright thus belongs to IFCA.
Contact author(s)
javier herranz @ upc edu
ramiro martinez @ upc edu
2022-01-14: last of 2 revisions
2021-04-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Javier Herranz and Ramiro Martínez and Manuel Sánchez},
      title = {Shorter Lattice-based Zero-Knowledge Proofs for the Correctness of a Shuffle},
      howpublished = {Cryptology ePrint Archive, Paper 2021/488},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.