Lattice-based proof of a shuffle

Published in Financial Cryptography and Data Security Workshop VOTING’19, 2019

In this paper we present the first post-quantum proof of a shuffle based on the learning with errors over rings (RLWE) problem. Shuffles are commonly used to construct mixing networks (mix-nets), a key element to ensure anonymity in many applications, and they are required to be universally verifiable, meaning that a proof of the shuffle must be generated and also published, so it can be verified by any observer. They should also guarantee long-term privacy in order to preserve anonymity against an attack using quantum computers. 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.

Download full version here