Paper 2019/357

Lattice-based proof of a shuffle

Núria Costa, Ramiro Martínez, and Paz Morillo


In this paper we present the first fully post-quantum proof of a shuffle for RLWE encryption schemes. Shuffles are commonly used to construct mixing networks (mix-nets), a key element to ensure anonymity in many applications such as electronic voting systems. They should preserve anonymity even against an attack using quantum computers in order to guarantee long-term privacy. The proof presented in this paper is built over RLWE commitments which are perfectly binding and computationally hiding under the RLWE assumption, thus achieving security in a post-quantum scenario. Furthermore we provide a new definition for a secure mixing node (mix-node) and prove that our construction satisfies this definition.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. 4th Workshop on Advances in Secure Electronic Voting (VOTING'19)
mix-netse-votingpost-quantumRLWE encryptionRLWE commitmentproof of a shuffle
Contact author(s)
ramiro martinez @ upc edu
2020-10-21: last of 2 revisions
2019-04-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Núria Costa and Ramiro Martínez and Paz Morillo},
      title = {Lattice-based proof of a shuffle},
      howpublished = {Cryptology ePrint Archive, Paper 2019/357},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.