Paper 2005/079

Zero-Knowledge Proofs for Mix-nets of Secret Shares and a Version of ElGamal with Modular Homomorphism

Marius C Silaghi


Mix-nets can be used to shuffle vectors of shared secrets. This operation can be an important building block for solving combinatorial problems where constraints depend on secrets of different participants. A main contribution of this paper is to show how participants in the mix-net can provide Zero-Knowledge proofs to convince each other that they do not tamper with the shuffled secrets, and that inverse permutations are correctly applied at unshuffling. The approach is related to the proof of knowing an isomorphism between large graphs. We also make a detailed review and comparison with rationales and analysis of Chaum's and Merritt's mix-nets. Another contribution is a (+ mod q, X)-homomorphic encryption scheme that can be parametrized by a public prime value q and that is obtained from (+,X)-homomorphic ElGamal. This cryptosystem allows for guarantees of security in the aforementioned mix-net. A generalization shows how to obtain modular arithmetic homomorphic schemes from other cryptosystems. Mix-nets offer only computational security since participants get encrypted versions of all the shares. Information theoretically secure algorithms can be obtained using secure arithmetic circuit evaluation. The arithmetic circuit previously proposed for shuffling a vector of size k was particularly slow. Here we also propose a new arithmetic circuit for performing the operation in O(k^2) multiplications and requiring k-1 shared random numbers with different domains. Another contribution is to provide more efficient arithmetic circuits for combinatorial optimization problems, exploiting recent secure primitives. Examples are shown of how these techniques can be used in the Secure Multi-party Computation (SMC) language. SMC's procedures for generating uniformly distributed random permutations are also detailed.

Note: ZK proof for the correctness of inverse permutations at un-shuffling detailed in the revision on April 16. Some citations added and a section removed on April 30. ElGamal version added on May 1

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
ElGamal modular homomorphismshuffling shared secrets mix-nethomomorphic encryption
Contact author(s)
msilaghi @ cs fit edu
2005-05-01: last of 22 revisions
2005-03-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marius C Silaghi},
      title = {Zero-Knowledge Proofs for Mix-nets of Secret Shares and a Version of ElGamal with Modular Homomorphism},
      howpublished = {Cryptology ePrint Archive, Paper 2005/079},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.