Proof of Shuffle Using Homomorphic Encryption (and ElGamal Encryption)
We all know how to shuffle (or mix) cards. But, a skilled dealer can trick us into thinking that cards have been shuffled, but where they manage to put certain cards in the right place. If done for gain, it is cheating, and if done for fun, it is probably a magical trick. Within an encryption system we can perform a blind shuffle where we can encrypt our data so that the dealer cannot see the cards that are being shuffled, and then for there to be a mixing process. In a trusted system, we have several nodes who each perform the same shuffle operation, and where we know that — if at least one node is honest, the shuffle will be honest. This is known as a mix-net.
In 2001, Neff [1] proposed a shuffling method that provides a proof of shuffle, and where each mix node does not require the public key of the cipher text. This is achieved using homomorphic encryption, such as using ElGamal or lattice methods:
In a re-encryption mix net, the input to the mixer is encrypted ciphertext. We then have a mixing phase where all the ciphertexts are shuffled and then re-encrypted. Next, we decrypt all the ciphertext. The mixer is normally done by…
