From: "Timothy C. May" <tcmay@got.net>
Date: Sun, 17 Nov 1996 19:13:42 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: Members of Parliament Problem
In-Reply-To: <v02140b00aeb57052428c@[192.0.2.1]>
Message-ID: <v03007800aeb58385887b@[207.167.93.63]>
MIME-Version: 1.0
Content-Type: text/plain


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."