0
$\begingroup$

I've been trying to create a distributed authorization protocol where identities are not revealed. Let me explain with an example.

Let's assume we have 4 actors, Alice, Bob, Charlie, and Dan. Alice is authenticating at Bob and Charlie's server and getting authorization from them. This authorization is valid for one-time use only. After that, Alice will send a request to Bob, Charlie, and Dan where she'll have to prove that she has the authorization without revealing her identity to them. And after 1 request, this authorization cannot be used again.

My Progress so far: I've been doing some research on Zero-Knowledge Proofs of Identity. The latest topic I've been reading up on is anonymous credentials. Using Anonymous credentials we can solve almost all the issues, but there is just one problem. So far as I know, after authenticating using anonymous credentials, you can use its proof as many times as you want. This completely takes away the on-time usage aspect of the authorization.

Can someone help me achieve the desired properties in my system?

$\endgroup$
3
  • $\begingroup$ I don't think both properties can be achieved at the same time. To give an authorization only usable once, the server must either save in memory a valid unused token, or an invalid used token. This token is an identifier. You can try to replace this token with something else, but my intuition is that to have an authorization limited to a number of uses (and not using a common external trusted third party or property, like the date), the server needs to save a counter (or a boolean in the case of 1 use max) tied to an identifier (the counter ID). $\endgroup$
    – A. Hersean
    Jun 7 at 13:07
  • $\begingroup$ You might want to look at "E-Cash Systems" ala Chaum. In these kind of systems there is the issue of "double spending" which seems to match your need to one-time usage $\endgroup$
    – AntonioFa
    Jun 10 at 14:32
  • $\begingroup$ @A. Hersean "Limited-show" means authorization is private a few times only, and would leak the identity if shown (token validity proven in zero knowledge) more than the pre-defined number of times. It assumes keeping records of authorization attempts. $\endgroup$ Jun 10 at 18:07
1
+100
$\begingroup$

Referring to Vadym Fedyukovych's answer:

Nullifier idea of ZCash could also help.

In this case, a proof is constructed with a nullifier, which is generated and kept by Alice, its hash is provided to Bob and Charlie, as a the Bob/Charlie's side of the authorization. If Alice wants to use this authorization, Alice must provide the nullifier to Bob and Charlie, and the authorization would be invalidated. Further attempts of using this nullifier would give an error stating that it has already been used. In this case, the authorization is associated with the nullifier, but not Alice herself.

Because the authorization can only be used once, we must add another number, provided by Bob or Charlie, known as the status-checker. This number, can be provided to Dan or any other party to check the status of the authorization, but not use it. The authorization is only considered used if Alice has disclosed the nullifier.

In conclusion, Alice may use the authorization by providing Bob or Charlie with the nullifier, and the authorization will be invalidated. Other parties may verify the validity of this authorization with the status checker.

For decentralization, the hash of the nullifier and Bob/Charlie's signature can be distributed, and by distributing the nullifier with Bob/Charlie's signature, the authorization is invalidated. In such a case, any third party (Dan in the example) may verify the status of the authorization without knowing Alice's identity, and only Bob/Charlie may nullify it. The employment of ring signatures may also conceal Bob and Charlie's identity as well.


Expansion to make this suit for most needs:

With the same example as yours, talking about Alice, Bob, Charlie and Dan. We disassociate any element in this system from the identities of Alice, Bob, Charlie and Dan, and associates them with their private/public key pairs. For each authorization, Alice generates a cryptographically secure random number n, which is both its authorization ID and nullifier. This n, is hashed and broadcasted, known as k. Bob/Charlie, upon receiving k, signs it and broadcasts the signature through the network. The signed message is broadcasted with another number generated by Bob/Charlie to be used to check the status. In such a way, there is an anonymous message on the network indicating that Bob/Charlie has authorized an anonymous figure. When Dan wants to check the status, he only needs to find the original authorization message, and whether there is a nullifier present. When Alice wants to use the authorization, she broadcasts the nullifier signed by Bob/Charlie, tagged with the status checking number, known as I. This message, if found by Dan, he would definitely know that the authorization has been used. Because there are no way of anyone else knowing the nullifier n, there are no way of tampering with the authorization.

$\endgroup$
0
$\begingroup$

The section 5.4 "Limited-show certificates" of the book "Rethinking Public Key Infrastructures" by S. Brands could be relevant, ISBN978-0262526302, and may be downloaded from Credentica.

The idea of nullifiers introduced by ZCash may also help.

$\endgroup$
1
  • 1
    $\begingroup$ Your original answer looks like a draft, and I have edited it. $\endgroup$
    – Red Sun
    Jun 12 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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