# Equivalents to a physical hat+shaking?

I would like a multiparty protocol, secure in the honest-but-curious model at least, but hopefully other situations as well, that can do the following: every party among $\{P_1, P_2, \ldots P_n\}$ puts in a value $v_i$, and the set of $v_i$'s is computed, in such a way that no one knows which party contributed which $v_i$. In the real world this can be done by putting folded slips of paper into a hat, but I cannot come up with a good search term. References are most appreciated.

-

You can solve this using mixnets.

Sample protocol:

1. The parties jointly choose a public/private keypair, such that the random key is shared among all $n$ parties. (This is threshold crypto, and there are standard protocols for this.)

2. Each party $P_i$ encrypts his/her value $v_i$ under the public key chosen in step 1. He/she broadcasts this ciphertext $E(v_i)$. Now everyone knows $E(v_1),\dots,E(v_n)$.

3. Party $P_1$ uses a re-encryption mixnet to shuffle and re-randomize the $n$ ciphertexts. Party $P_1$ uses a zero-knowledge proof to prove that he/she did this step honestly (i.e., the shuffled ciphertexts decrypt to the same set of values as the original ciphertexts did). He/she broadcasts the results and the zero-knowledge proof. (There are standard protocols for this.)

4. Party $P_2$ does the same thing: he/she uses a re-encryption mixnet to shuffle and re-randomize the $n$ ciphertexts that resulted from step 3.

5. And so on. Each party in turn performs their own re-encryption mix on the results from the previous party. At the end of this, party $P_n$ has broadcast a set of ciphertexts $C_1,\dots,C_n$ that are a shuffled and re-randomized version of $E(v_1),\dots,E(v_n)$.

6. Now all the $n$ parties use the threshold decryption protocol to jointly decrypt the ciphertexts $C_1,\dots,C_n$ and broadcast the result. As a result, everyone learns the values $v_1,\dots,v_n$, but in a shuffled/permuted order that cannot be linked to the originator of each value.

This should satisfy your goals. I think it provides about as much security as one could hope for: if a party is honest, she can verify the integrity of the result of the protocol; and if $k$ parties are honest and $n-k$ parties are dishonest, then the dishonest parties learn the set of $k$ values that were contributed by the $k$ honest parties, but cannot associate which of those $k$ values came from which honest party.

-