Re: Members of Parliament Problem
At 1:23 PM 11/17/1996, Timothy C. May wrote:
At 11:43 AM -0800 11/17/96, Peter Hendrickson wrote: For the specific example Peter cites, of a member of Parliament who doesn't like the possibility of anonymity....well, he wouldn't be part of the DC-Net would he? Generally, there are no cryptographic solutions that will encompass the case where some member wants to speak anonymously, but no one else does. If a message originates from "someone in Parliament," but only one member of Parliament is set up to speak anonymously, then of course by simple elimination he is the speaker. As before, this is beyond any cryptographic solution.
It turns out - amazingly enough - that this is not true! Hal Finney mentioned on Friday a paper by Chaum and Heyst entitled "Group Signatures." It was presented at EuroCrypt '91. I scanned this paper today and it has four schemes, the last of which requires no participation of a trusted party or the other people one wishes to hide amongst. So long as everybody has published their public key, the rogue Member of Parliament can sign messages without revealing his identity, yet demonstrating that he is in fact a Member of Parliament. (Thanks Hal!) It uses a zero-knowledge proof. Hal said earlier that it was not clear to him that this could be turned into a non-interactive proof. It isn't clear to me, either. Whatever the case, I consider the problem solved. It would be nice if it were non-interactive, but the rogue MP need only demonstrate his identity to ten or so publicly trusted parties to have enough basis to make statements that the world will consider to be credible.
There may be easier to implement approaches, such as the ones people have proposed involving distribution of "voting tokens" (blinded, for anonymity).
Anonymous voting is, in fact, formally equivalent (with some hand-waving about some details) to the problem of untraceable speaking. The example Peter cited, of a MP wanting to "speak anonymously" is equivalent to wanting his vote--on Northern Ireland, for example--to be anonymous.
I would say that it is slightly different in that anonymous voting requires that you guarantee that each voter votes only once. Clearly these are similar problems. Tangentially, I would really enjoy the privilege of verifiable anonymous voting using my computer. As it is now, I have no way of telling whether my vote counts or not. The entire process is handled by people I don't know and have no particular reason to trust.
A simple form of this is "blackballing." Members have white and black balls, and place one of the balls in an urn. Properly implemented, this gives anonymity.
I always wondered where that term came from. Chaum and Heyst's protocol above could be used for blackballing in cases where only one black ball can make the decision. For instance, some clubs have a rule that any current member can "blackball" prospective members. (Sounds harsh? Not as harsh as learning that a *majority* of the club didn't like you!) Peter Hendrickson ph@netcom.com
At 6:32 PM -0800 11/17/96, Peter Hendrickson wrote:
At 1:23 PM 11/17/1996, Timothy C. May wrote:
At 11:43 AM -0800 11/17/96, Peter Hendrickson wrote: For the specific example Peter cites, of a member of Parliament who doesn't like the possibility of anonymity....well, he wouldn't be part of the DC-Net would he? Generally, there are no cryptographic solutions that will encompass the case where some member wants to speak anonymously, but no one else does. If a message originates from "someone in Parliament," but only one member of Parliament is set up to speak anonymously, then of course by simple elimination he is the speaker. As before, this is beyond any cryptographic solution.
It turns out - amazingly enough - that this is not true!
Hal Finney mentioned on Friday a paper by Chaum and Heyst entitled "Group Signatures." It was presented at EuroCrypt '91.
I scanned this paper today and it has four schemes, the last of which requires no participation of a trusted party or the other people one wishes to hide amongst. So long as everybody has published their public key, the rogue Member of Parliament can sign messages without revealing his identity, yet demonstrating that he is in fact a Member of Parliament. (Thanks Hal!)
OK, so let's make my example concrete. Ten people form a group such as we have been discussing. A message emanates from the group at some time. Nine of the members are actually FBI agents. They know they didn't issue the message. (I mentioned the meta-issue of their lying, so no smart aleck comments about the FBI planting the message!). Q.E.D., any message must've come from the 10th member. All the zero knownledge and DC-Net software in the world can't change this basic existential truth. This was my point that "this is beyond any cryptographic solution." Please explain, Peter, how your example of signing messages but not revealing identity precludes this meta-cryptography means of revealing identities? So far as know, in _any_ N-party cryptographic game, if N - 1 are acting as one (colluding, sharing), this reduces to a 2-party game. And the second party can always know if he was the source of a message or not. If he was not, the message must have come from the other party. (If I am wrong on this, I'll be shocked, and pleasantly surprised that crypto has revealed something amazing. I rather doubt I will.) --Tim May "The government announcement is disastrous," said Jim Bidzos,.."We warned IBM that the National Security Agency would try to twist their technology." [NYT, 1996-10-02] We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."
participants (2)
-
ph＠netcom.com -
Timothy C. May