Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.