Lattice-based proof of a shuffle

Published in (under review), 0000

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.