Lattice-based proof of a shuffle
Published in Financial Cryptography and Data Security Workshop VOTING’19, 2019
Recommended citation: Costa N., Martínez R., Morillo P. (2020) Lattice-Based Proof of a Shuffle. In: Bracciali A., Clark J., Pintore F., Rønne P., Sala M. (eds) Financial Cryptography and Data Security. FC 2019. Lecture Notes in Computer Science, vol 11599. Springer, Cham https://doi.org/10.1007/978-3-030-43725-1_23
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.