Zero-knowledge identification of the majority commitment

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?

Answer 1

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)

Answer 2

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.