Re: Members of Parliament Problem

[Hal Finney <hal@rain.org>]

From: ph@netcom.com (Peter Hendrickson)
> At 1:39 PM 11/17/1996, Simon Spero wrote:
> > 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.

The 4th method of Chaum's, from Eurocrypt 91, somewhat satisfies this,
as does a method from the Eurocrypt 94 paper.  Each person can choose
his own public key g**x for a discrete log system.  However, the problem
is that all members of the group have to choose the same prime p as the
modulus, and generator g, for their discrete logs.

The issue of using a common modulus in discrete log systems has been
somewhat controversial.  I think when the government first proposed DSS
they planned to do something like this, one modulus with everyone having
different secret x values with corresponding public keys y = g**x mod p.
This has the advantage that public keys are smaller since everyone uses
the same g and p.  So all you need is one value for your public key.
Without this you have to have g, y, and p be your public key so it is
3 times bigger.

The problem is that the way the main discrete log algorithms work,
once you have broken one discrete log for a certain g and p you can break
all the others very easily.  So the particular g,p pair which is chosen
for everyone to share becomes one very big, fat target to try to apply
discrete log algorithms.

Now this is not necessarily as bad as it seems.  Unlike the case with RSA,
there is no secret information which could be leaked to make solving these
discrete logs easier.  Nobody knows how to do it.  So the only way it can
be done is by a massive operation roughly similar to factoring an RSA
modulus the size of p.  Choosing p of 1000 or 2000 bits should still make
it effectively impossible for anyone to do this.  The numbers are simply
far too large.

Still the consensus of opinion with discrete logs is that the advantages
of slightly smaller keys have not been great enough to justify the risk
involved in having eveyone share a modulus, even though that risk is
seemingly insignificant.  On the other hand maybe for cases like this
the additional advantages to common moduli would be enough to tilt the
argument in the other direction.

Hal