Welcome to the resource topic for 2012/301
Title:
A Public Shuffle without Private Permutations
Authors: Myungsun Kim, Jinsu Kim, Jung Hee Cheon
Abstract:In TCC 2007, Adida and Wikström proposed a novel approach to shuffle, called a public shuffle, in which a shuffler can perform shuffle publicly without needing information kept secret. Their scheme uses an encrypted permutation matrix to shuffle ciphertexts publicly. This approach significantly reduces the cost of constructing a mix-net to verifiable joint decryption. Though their method is successful in making shuffle to be a public operation, their scheme still requires that some trusted parties should choose a permutation to be encrypted and construct zero-knowledge proofs on the well-formedness of this permutation. In this paper, we propose a method to construct a public shuffle without relying on permutations and randomizers generated privately: Given an n-tuple of ciphertext (c_1,\dots,c_n), our shuffle algorithm computes f_i(c_1,\dots,c_n) for i=1,\dots,\ell where each f_i(x_1,\dots,x_n) is a symmetric polynomial in x_1,\dots,x_n. Depending on the symmetric polynomials we use, we propose two concrete constructions. One is to use ring homomorphic encryption with constant ciphertext complexity and the other is to use simple ElGamal encryption with linear ciphertext complexity in the number of senders. Both constructions are free of zero-knowledge proofs and publicly verifiable.
ePrint: https://eprint.iacr.org/2012/301
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .