3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Sorry, I thought this site was for general algorithms questions. Should I move it to these sites or create a new question there? $\endgroup$
    – Anatoli
    Mar 13, 2014 at 23:30

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Anatoli
    Mar 14, 2014 at 5:30
  • $\begingroup$ 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. $\endgroup$
    – Anatoli
    Mar 14, 2014 at 5:34
  • $\begingroup$ 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. $\endgroup$
    – Anatoli
    Mar 14, 2014 at 5:35
  • $\begingroup$ 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. $\;\;\;\;$ $\endgroup$
    – user991
    Mar 14, 2014 at 7:25
  • $\begingroup$ 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. $\endgroup$
    – Anatoli
    Mar 14, 2014 at 7:35
2
$\begingroup$

A paper was published in 2015 describing a scheme called Anonize to do just that.

It appears to be constructed around a specially designed Non-Interactive Zero-Knowledge Proof of Knowledge (NIZKPoK) protocol used by clients.

First, a registration is made, whereby a client sends a commitment to a seed of a pseudo-random function. Sent back to it by the Server is the Server's signature on that commitment and the client's id, which becomes that client's master token. Then the client uses the seed to generate a single-use token. Finally, to submit a response the client has to prove by NIZK that it knows some master token, a survey conductor's signature authorizing some client to go through the survey, and that it indeed computed the single-use token by the seed it knows.

It's notable that the scheme actually makes it possible to conduct multiple ad-hoc surveys on a single server, without giving the server's operator an opportunity to track clients across multiple surveys. That is achieved by using a survey id, which is different for every survey, to generate single use tokens. A client can, on the other hand, only generate one single-use token for each survey id, which means it will only be able to submit one answer.

A usable online implementation can be found here and the development reference implementation is hosted over here.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Anatoli
    Mar 14, 2014 at 5:51
  • $\begingroup$ @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. $\endgroup$
    – rath
    Mar 14, 2014 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.