Re: Members of Parliament Problem

At 1:39 PM 11/17/1996, Simon Spero wrote:
>On Fri, 15 Nov 1996, Rich Graves wrote:
>>Peter Hendrickson wrote:
>>> There are times when one wishes to speak anonymously, yet speak
>>> as a member of a group.

>> You either need to trust a shared server to know and then blind your
>> identity, or trust the people with whom you share a secret key not to
>> give that key to non-group members.

> Why not use  blinding for obtaining the certificate?

> Create a number up public/private key pairs, blind them, then do the
> cut-and-choose thing with the security officer. He signs the blinded key,
> then returns it. Unblind the remaining pubic key, and you've got a public
> key with the appropriate signature on it.

Okay, this would work.  But, it requires that all (or at least many) of the
Members of Parliament cooperate.  If not, then the security officer will
be able to make very good guesses about who is speaking.

Parliamentarians may not cooperate for a variety of reasons.  They may
not wish to be attacked by terrorists for the words of others.  They
may believe that cowardice is not to be encouraged.  They may not believe
in anonymity.  It might be too hard for them.

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

Peter

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

Peter Hendrickson wrote:
> 
> At 1:39 PM 11/17/1996, Simon Spero wrote:
> >
> > Why not use  blinding for obtaining the certificate?
> 
> > Create a number up public/private key pairs, blind them, then do the
> > cut-and-choose thing with the security officer. He signs the blinded 
> > key, then returns it. Unblind the remaining pubic key, and you've 
> > got a public key with the appropriate signature on it.
> 
> Okay, this would work.  But, it requires that all (or at least many) 
> of the Members of Parliament cooperate.  If not, then the security 
> officer will be able to make very good guesses about who is speaking.
> 
> Parliamentarians may not cooperate for a variety of reasons.  They may
> not wish to be attacked by terrorists for the words of others.  They
> may believe that cowardice is not to be encouraged.  They may not x
> officer will in anonymity.  It might be too hard for them.

Moreover, parliamentarians from different sides of the aisle usually
have different points of view, and an interest in "outing" each other.
A parliament where everyone had the same point of view would be
uninteresting for this problem -- your friendly local terrorist would
just blow up the whole building.

A practical example of this kind of thing is the situation of judges
in Colombia.

-rich