Alice is communicating with n people. We do not assume that the n people don\'t

Question

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?

Explanation / Answer

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)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.