A verifiable shuffle for the GSW cryptosystem

Abstract

This paper provides the first verifiable shuffle specifically for fully homomorphic schemes. A verifiable shuffle is a way to ensure that if a node receives and sends encrypted lists, the content will be the same, even though no adversary can trace individual list items through the node. Shuffles are useful in e-voting, traffic routing and other applications. We build our shuffle on the ideas and techniques of Groth’s 2010 shuffle, but make necessary modifications for a less ideal setting where the randomness and ciphertexts admit no group structure. The protocol relies heavily on the properties of the so-called gadget matrices, so we have included a detailed introduction to these. Keywords: verifiable shuffle, fully homomorphic encryption, postquantum