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