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.

Alice is communicating with $n$ people. We do not assume that the $n$ people don't trust each other or trust Alice. Alice doesn't trust them either, and needs to assume that they will not form a coalition against her, so we assume the $n$ people cannot communicate with each other (except through Alice, if she agrees). Each of the $n$ people owns a secret bit $0$ or $1$. Let $m$ be the majority value, i.e., the bit owned by the largest number of people. (We assume that it is unique.)

Is it possible to design a protocol so that the $n$ people can commit to their value to Alice, and Alice can find out which of the people committed to the majority value $m$ without knowing what the value of $m$ is or gaining any other information about the values?

share|improve this question
add comment

2 Answers

Here is one difficultly such a protocol can have: say we do have a joint computation protocol that takes $N+1$ parties (Alice and her $n$ people); at the end of the protocol, Alice gets a list of the parties in the majority without learning their secret.

Here is how Alice can attempt to cheat: extend the protocol to $N+3$ parties, and have the extra two parties be two artifical votes controlled by Alice; thing0 will submit a 0 vote, and thing1 will submit a 1 vote; other than that, the protocol continues as is. thing0 and thing1's vote will not change which bit was in the majority; however, when Alice gets a list of the majority party; either thing0 or thing1 will be in the list; by that, Alice will learn the secret bit.

Any such protocol will need to avoid this somehow; either by simply not being extensible to N+3 parties, or having each party get a count of how many people are participating (so that they'll know that there are two extra ringers)

share|improve this answer
    
More generally, if any of the $n$ people reveals their bit to Alice, then Alice knows the value of $m$ (and knows everybody's bit, since she knows who chose the majority value). –  Gilles Feb 5 '13 at 12:57
add comment

Putting ponchos comment aside for the moment:

What if Alice were to ask all parties to hash their commitments in a deterministic way (no padding, no salt, etc.) and then send it to her. She would be able to tally the majority and know who took part in it. There would only be a problem if the set or size of commitments were so small that Alice would be able to find out the input values of the hash function. As far as I can tell to be absolutely sure all n parties need to agree on a common secret (pre-shared certificates, encryption key, salt, etc.) with Alice as a man in the middle attacker.

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.