Cryptology ePrint Archive: Report 2021/488

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

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

Abstract: 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.

Category / Keywords:

Original Publication (with minor differences): to be published in the Proceedings of VOTING'2021 (Financial Cryptography Workshops). The copyright thus belongs to IFCA.

Date: received 16 Apr 2021, last revised 6 May 2021

Contact author: javier herranz at upc edu, ramiro martinez@upc edu

Available format(s): PDF | BibTeX Citation

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) We have changed the set of parameters suggested in Section 4.1, because the previous ones were incorrect; we warmly thank Tjerand Silde for pointing out such a mistake (which will appear in the proceedings version) to us.

Version: 20210506:141943 (All versions of this report)

Short URL: ia.cr/2021/488


[ Cryptology ePrint archive ]