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.Category / Keywords: ElGamal modular homomorphism, shuffling shared secrets mix-net, homomorphic encryption Date: received 9 Mar 2005, last revised 1 May 2005 Contact author: msilaghi at cs fit edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation 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 Version: 20050501:154520 (All versions of this report) Discussion forum: Show discussion | Start new discussion