Re: Members of Parliament Problem

[Hal Finney <hal@rain.org>]

From: paul@fatmans.demon.co.uk
> You could also have an arbitrated blind signature protocol whereby 
> trent shares a keypair with all users. bob encrypts his comment, M 
> with the key he shares with trent. On recieving it trent carries out 
> a blind signature on it and publishes it, as trent knows only bob has 
> the shared key, K he knows bob said M but as it is a blind sigature 
> and he is likely to be signing a lot of messages (trent is of course 
> a computer program) he doesn`t know which message came from bob.

I don't quite follow how this would work.  If Trent issues a blind
signature, then that means (doesn't it?) that he doesn't see what he
is signing.  So how can he confirm that the message is actually from
a member of the group when he doesn't see it?

> Also Chaums group signatures could be used but unfortunately the 
> arbitrator can find out who said what, but does not normally know.
> Also trent can forge digital signatures with this protocol.
> Chaum further mentions protocols for this sort of thing that do not 
> even need an arbitrator but I don`t have the papers on this.

Not all of Chaum's proposals in the original paper from Eurocrypt 91
have this property.  Here is what he has, somewhat simplified.  Z is
the trusted party for those protocols which use one.

1) Each group member makes up a key which he will use for one signature.
Z signs each key to certify that it is a member of the group.  People
don't re-use keys so that messages are unlinkable.  Z can tell who sent
which message since he knows the keys.

2) Z publishes an RSA modulus N, gives each group member a secret exponent
si, and publishes v = the product of all the si.  Members sign message m
by producing m**si mod N.  Then to confirm the signature they engage in a
zero knowledge protocol to prove that the signature is of the proper form
and that si divides v (without revealing si).  Chaum gives a protocol for
this.

3) Z again publishes an RSA modulus N, and each group member chooses his
own RSA modulus Ni = pi * qi.  To sign message m he produces m**pi mod N.
He then proves in zero knowledge that the signature is of the proper
form and that pi divides the product of all the Ni (without revealing pi).
This is the same zero knowledge protocol as in (2) above.

4) Members agree on a large public prime p with generator g.  Each member
chooses a secret exponent si with public key ki = g**si mod p.  (This is a
standard discrete log cryptosystem setup.)  To sign message m he produces
m**si mod p.  He must then prove in zero knowledge that the signature
is of the proper form and that si is the private exponent corresponding
to the public key of some group member, without revealing exactly which
group member it is for.  The protocol for this is not very efficient.
It uses a cut and choose concept and has to be iterated multiple times.

In methods 1, 2, and 3, Z can tell who made a signature.  In method
2, Z can forge signatures for other members.  Method 4 doesn't use
a trusted party.

Method number 4 is very similar to Chaum's original proposal for
undeniable signatures, although the zero knowledge proof is very different
since he doesn't want to reveal which particular key his exponent
corresponds to.

In the Eurocrypt 94 paper by Chen and Pederson they show a very nice
protocol for proving that you know the exponent corresponding to
one of a set of Diffie Hellman public keys.  This is similar to the
problem in (4) above.  Given k1=g**s1, k2=g**s2, ..., you can prove
that you know one of the si without revealing which one.  The protocol
is pretty simple and just requires one challenge and response, although
the amount of data sent is proportional to the number of ki in the set.

This could be used to prove group membership anonymously.  If there
were a list published of public keys of people on the cypherpunks list,
you could prove you were on that list without revealing your identity.
I think it could be made a signature protocol by having the challenge
c depend on a hash of the message.  But the authors don't do it that
way, they do a more complicated protocol because they are seeking to
achieve unconditional rather than cryptographic anonymity.

Hal