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