Paper 2005/137

A Sender Verifiable Mix-Net and a New Proof of a Shuffle

Douglas Wikström


We introduce the first El Gamal based mix-net in which each mix-server partially decrypts and permutes its input, i.e., no re-encryption is necessary. An interesting property of the construction is that a sender can verify non-interactively that its message is processed correctly. We call this sender verifiability. We prove the security of the mix-net in the UC-framework against static adversaries corrupting any minority of the mix-servers. The result holds under the decision Diffie-Hellman assumption, and assuming an ideal bulletin board and an ideal zero-knowledge proof of knowledge of a correct shuffle. Then we construct the first proof of a decryption-permutation shuffle, and show how this can be transformed into a zero-knowledge proof of knowledge in the UC-framework. The protocol is sound under the strong RSA-assumption and the discrete logarithm assumption. Our proof of a shuffle is not a variation of existing methods. It is based on a novel idea of independent interest, and we argue that it is at least as efficient as previous constructions.

Note: Kun Peng claims, (International Journal of Network Security & Its Applications (IJNSA), Vol.3, No.1, January 2011) that the soundness of this protocol fails. This claim, and the other claims he makes about zero-knowledge and "correctness" are wrong. Before you decide to cite these wrong claims, make sure you read and understand my paper and please do not hesitate to contact me if something is not clear.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
cryptographic protocolsmix-netanonymous channelshuffleelectronic election
Contact author(s)
dog @ nada kth se
2011-10-24: last of 6 revisions
2005-05-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Douglas Wikström},
      title = {A Sender Verifiable Mix-Net and a New Proof of a Shuffle},
      howpublished = {Cryptology ePrint Archive, Paper 2005/137},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.