A Verifiable Shuffle for the GSW Cryptosystem
We provide 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
- PDF / 295,551 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 52 Downloads / 212 Views
stract. We provide 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 Post-quantum
1
· Fully homomorphic encryption ·
Introduction
A verifiable shuffle is used to prove that two sets of ciphertexts will decrypt to the same values, but without revealing how the sets relate. Such shuffles are well-known for group homomorphic schemes, and are still being developed and improved. Today, shuffles are particularly useful in e-voting and mixnets, in order to make it hard to correlate the input and the output of a node. Fully homomorphic encryption has also been suggested as a useful primitive for both e-voting [10] and private network routing. Complex voting systems in particular can take advantage of the features of fully homomorphic encryption, but the FHE toolbox is still missing a number of useful protocols. Recent development have brought shuffling for FHE within reach. Our result starts from Groth’s 2010 shuffle [11], which uses an idea from Neff [15]. A polynomial (X−x1 )(X−x2 ) · · · (X−xn ) is obviously unchanged when the roots are permuted. One can then ask the prover to evaluate the polynomial at random points. The probability of two nonidentical polynomials evaluating to the same value at a random point is negligible. While later development have resulted in even more efficient protocols, Groth’s 2010 approach has the advantage of simplicity and that there are few compromises: the protocol satisfies a standard soundness condition and it is honest-verifier zero knowledge. We return to the details in Sect. 2. c International Financial Cryptography Association 2019 A. Zohar et al. (Eds.): FC 2018 Workshops, LNCS 10958, pp. 165–180, 2019. https://doi.org/10.1007/978-3-662-58820-8_12
166
M. Strand
The polynomial mentioned above is hidden in a subprotocol which is used to prove correctness of a shuffle of known content. The subprotocol is completely independent of the encryption scheme, and uses only a homomorphic commitment scheme. It is important to note that the commitment scheme need only be homomorphic with respect to a single operation. We return to the selection of such schemes. The protocol is then completed by binding the secret data – which we want to prove the claim for – to the known content for which one can prove the relation. Groth’s protocol depends crucially on the fact that some group homomorphic schemes are homomorphic both with respect to the message and the randomness. For instance, the pr
Data Loading...
