International Association
for Cryptologic Research

In TCC 2007, Adida and Wikstr\\\"{o}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.