Paper 2020/115

A Verifiable and Practical Lattice-Based Decryption Mix Net with External Auditing

Xavier Boyen, Thomas Haines, and Johannes Mueller


Mix nets are often used to provide privacy in modern security protocols, through shuffling. Some of the most important applications, such as secure electronic voting, require mix nets that are verifiable. In the literature, numerous techniques have been proposed to make mix nets verifiable. Some of them have also been employed for securing real political elections. With the looming possibility of quantum computers and their threat to cryptosystems based on classical hardness assumptions, there is significant pressure to migrate mix nets to post-quantum alternatives. At present, no verifiable and practical post-quantum mix net with external auditing is available as a drop-in replacement of existing constructions. In this paper, we give the first such construction. We propose a verifiable decryption mix net which solely employs practical lattice-based primitives. We formally prove that our mix net provides a high level of verifiability, and even accountability which guarantees that misbehaving mix servers can also be identified. Verification is executed by a (temporarily trusted) public auditor whose role can easily be distributed. To demonstrate practicality for real-world systems, we provide detailed performance benchmarks on our stand-alone implementation based only on the most conservative lattice hardness assumptions.

Available format(s)
Publication info
Preprint. MINOR revision.
lattice-basedverifiabilityaccountabilitymix nete-voting
Contact author(s)
johannes mueller @ uni lu
2020-04-27: revised
2020-02-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xavier Boyen and Thomas Haines and Johannes Mueller},
      title = {A Verifiable and Practical Lattice-Based Decryption Mix Net with External Auditing},
      howpublished = {Cryptology ePrint Archive, Paper 2020/115},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.