At 11:43 AM -0800 11/17/96, Peter Hendrickson wrote:
What I would like to see is a method which relies only on published public keys and no other cooperation from the people who are (more or less) being used as shields. This may be impossible.
(A number of people have posted references to other ways of doing this. I have yet to track down the references they gave so I don't know if any of them fit the bill.)
It sounded to me from your initial statement of the problem that this is the canonical Dining Cryptographers Problem: a group of N persons wishes to allow communication from one of their number without any possibility that the message can be traced to a single one of them. There are of course numerous issues to be dealt with in a DC-Net, some discussed in Chaum's orginal paper (available at one time at the Cypherpunks ftp site), some discussed in the followup papers in "Eurocrypt" some years back, and some discussed by several of us on this list (with, perforce, not as much academic rigor as the academic papers have). * Collusion. It will _always_ (repeat: always) be possible for N -1 of the folks to conspire to identify the member sending the message. No cryptographic system can possibly prevent that, for basic ontological reasons. (For example, if the members of Parliament suspect MP Peter H. to be the source of anti-British opinions, they may compare notes, agree that none of them sent the message, and thus know that Peter H. sent it. Of course, can they be trusted? A meta-issue. But such are the ways even DC-Nets can be thwarted...by the members themselves. This is beyond cryptography.) However, the costs and difficulties in collusion to identify a sender can be made quite high by having multiple DC-Nets, such that collusion would have to span a critical subset of them. * Denial of service. Some members of the DC-Net(s) may choose not to participate, or to "lie" (in terms of doing their XOR operations with their neigbor), etc. The various DC-Net papers deal with these problems. 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. And as soon as N are interested, where N > 1, the possibility of a DC-Net is present. Obviously, the bigger N is, the better. 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. (Chaum was studying anonymous electronic voting protocols, of course.) 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. --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."