# Group membership with unique anonymous claims

Is it possible to accomplish the following scheme?

There is a Server (S) and many clients.

Each client enrolls with S, exposing its real identity; S saves the real identity information in its database and executes some keys/identifiers exchange with each client (could be something like DHE or RSA).

Then, someone sends to S a claim such that S would be able to tell that this claim comes from one of the enrolled clients, but not being able to identify from which one (inability similar to factoring large prime numbers). At the same time S should be able to save it and only accept 2 more claims from the remaining clients (i.e. the client that have sent a claim can't send it again).

No client should have such information that, if leaked, could invalidate the entire scheme. In other words, any exposure of the identifier of a single client should only put in danger the ability of this client to make its claim.

A case: 3 clients (X, Y and Z) enroll with S.
X makes a claim to S.
S verifies that it comes from one of the clients and saves it, notifying the client that the claim was accepted. S does NOT know that the claim came from X. At this point, S only knows that 2 of the 3 claims remain.
Z makes its claim. S verifies and accepts it.
At this point S knows that only 1 claim remains.
X sends its claim again. S finds that it was already claimed and rejects it.
Y sends it claim. S verifies and accepts it.
At this point, S knows that all the claims were made.

-

## migrated from cstheory.stackexchange.comMar 14 '14 at 0:07

This question came from our site for theoretical computer scientists and researchers in related fields.

Sorry, I thought this site was for general algorithms questions. Should I move it to these sites or create a new question there? –  Anatoli Mar 13 '14 at 23:30

If "S assigns to each of them a unique identifier" then S could just run the claim
algorithm with each of those identifiers to find out who a given claim was from.

Something similar would be to have S blindly sign a perfectly binding commitment
that is generated by the client, to the identifier that is assigned by the server.

-
I've updated the quoted part in the question. The key/identifier the client receives from S should not necessarily be the one the client will later send as-is to the server and not necessarily be the one the server generates (could be some value generated by the client). Some derivations from it could be performed at the enrolment stage and at the claim stage. This is actually the part I'm not sure it's possible at all, and if it is, what it should be like. And blind signature indeed looks like solving the problem. –  Anatoli Mar 14 '14 at 5:30
Please confirm the following implementation would work without any issues for the defined requirements of the scheme: A client generates some identifier and asks S to blind sign it providing its real identity (the enrolment stage). Then it can later send the signed unblinded identifier to S, S verifies that it has a correct signature and that it was not previously accepted, so S accepts it as a claim without knowing the real identity of the client. S saves the identifier and as it's the only signed identifier the client has, it can't make a claim twice. –  Anatoli Mar 14 '14 at 5:34
At the same time, as the client and only it has its identifier, no other party could use the client's right for a claim. I think the perfectly binding commitment is not even necessary in this case. –  Anatoli Mar 14 '14 at 5:35
That would work. $\:$ The perfectly binding commitment would ensure that if all parties are honest $\hspace{.55 in}$ then there is zero probability of a(n incorrect) rejection. $\;\;\;\;$ –  Ricky Demer Mar 14 '14 at 7:25
Ricky, thanks for you answer. It looks like a perfect match for the question. I'll leave it open for some days for other users to answer and comment and then accept the best answer. –  Anatoli Mar 14 '14 at 7:35

Introducing three modifications:

• Assume part of a client's "real identity" is a public key $U_P$, generated by the client
• There exists an oracle $V$ acting as a verifier
• The server gives each client its public key $S_P$

If the clients know each other, or some of the others, they can also verify they all have the same $S_P$.

Setup:

$S$ makes the list of user keys available to $V$.

Execution:

A client first encrypts a claim $M$ for the server $M'\leftarrow\operatorname{Enc}(M, S_P)$ and then signs $M'$ to obtain

$$M'_U\leftarrow\operatorname{Sign}(\;M', U_P)$$

and sends $M', M'_U$ to $V$, who keeps the tally for each user. If the user hasn't yet submitted a claim, $V$ signs the message with its own key to get

$$M'_V\leftarrow\operatorname{Sign}(\;M', V_P)$$

It also generates a reference number $N$ which encrypts and sends back to $U$.

and finally forwards $M', M'_V, N$ to $S$.

The server can now route the result back to the client through $V$ or announce to everyone that "$N$ is complete".

Caveats:

1. Essentially authentication and claims handling has been separated. Not sure if this works for you but it conforms to requirements.

2. You're trying to solve the double spending problem with (1) a centralized structure while (2) retaining anonymity. Getting rid of $V$ would be possible if you dropped one of the two, ie. if you introduced some P2P or by making claims identifiable by the server.

-
If I understood it correctly, V will know the real identities of the clients, so it'll be able to communicate to S that M' and M'v belong to a particular client, right? The main requirement is for the client to maintain its anonymity with the verification side (S split in 2 or more entities or as a single entity) when making a claim. –  Anatoli Mar 14 '14 at 5:51
@Anatoli $V$ knows the public keys of the clients, not necessarily their real identities. Yes, that is correct, but Ricky Demer's solution (the one you describe in your comments) is much simpler and should be preferred. –  rath Mar 14 '14 at 5:54