Proving membership of a group without revealing identity?

Question

I have an interesting problem for which I've failed, so far, to find an elegant solution.

Imagine that a user needs to repeatedly prove to public observers that they are a member of a trusted set but the proof needs to be different each time so that they can't be tracked.

My initial thought was that the set owner publishes the value of an RSA Accumulator which includes all the members and each member possesses the corresponding witness value. They can then reveal the witness, and an observer can confirm that they are indeed included in the accumulator. The problem with this is the witness (proof) is constant so every time they assert their membership, observers can infer their identity. Also any observer can then steal their proof and use it themselves. I don't want the member to have to contact the set owner before each assertion e.g. get them to blind sign each new assertion.

I've also looked at Paillier based homomorphic encryption where the user could deliberately blind a value by adding to it but, here the keys are the wrong way around i.e. public encrypts and private decrypts. The set owner would need the private key. So what I really need is a homomorphic signature where the owner can give the user a signed value which can be blinded for each use.

What would you recommend to solve this problem?

Answer 1

Look at group signatures (but use one of the more modern schemes; they are proven secure). The signature can be applied to a running counter, or a random challenge. Group signatures also give you a lot of "management" options which can be useful depending on the application. If you don't need them, then you can use ring signatures (but the verifier has to check that the ring includes only members of the set, or someone else can easily join).