Paper 2012/301

A Public Shuffle without Private Permutations

Myungsun Kim, Jinsu Kim, and 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
secret shufflepublic shuffleprivate permutationmix-netElGamal encryption
Contact author(s)
msunkim @ snu ac kr
kjs2002 @ snu ac kr
jhcheon @ snu ac kr
History
2012-06-24: revised
2012-06-03: received
See all versions
Short URL
https://ia.cr/2012/301
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/301,
      author = {Myungsun Kim and Jinsu Kim and Jung Hee Cheon},
      title = {A Public Shuffle without Private Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2012/301},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/301}},
      url = {https://eprint.iacr.org/2012/301}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.