Welcome to the resource topic for 2021/488
Title:
Shorter Lattice-based Zero-Knowledge Proofs for the Correctness of a Shuffle
Authors: Javier Herranz, Ramiro Martínez, 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.
ePrint: https://eprint.iacr.org/2021/488
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .