From: ph@netcom.com (Peter Hendrickson)
Date: Sun, 17 Nov 1996 18:32:33 -0800 (PST)
To: "Timothy C. May" <cypherpunks@toad.com
Subject: Re: Members of Parliament Problem
Message-ID: <v02140b00aeb57052428c@[192.0.2.1]>
MIME-Version: 1.0
Content-Type: text/plain


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