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