A Zero knowledge proof for set membership?

Question

Essentially, I am trying to build up a list of authorised public keys that will be stored in a database P by a verifier V. A public key will be considered authorised if belongs to a user in a database of verified users D. The problem is that it should not be possible for the verifier to ever link a public key to a specific authorised user.

I was thinking something along the following lines - Every user in D hashes a secret message that gets stored along with their account in D:

+-------+--------+
| User  |  Hash  |
+-------+--------+
| Bob   | abc123 |
| Alice | xyz789 |
| Eve   | 456fgh |
+-------+--------+

Then some sort of cryptographic accumulator can be used to combine the hashes. When a user wants to authorise their public key, they prove to V (in zero knowledge) that they know a message that when hashed, forms part of the accumulator. If V is able to confirm this, there public key is added to P, otherwise it is rejected.

To make matters even more complicated, a user should only be able to ever have one public key in P. In other words, Bob must not be able to continuously request multiple keys to be added to P. Thus, once everyone has had a public key authorised, P will look as follows:

+--------+
|   PK   |
+--------+
| MXH452 |
| B6HGJS |
| 67ZC6S |
+--------+

With it being impossible to know which public key belongs to which user. All we know is those public keys are verified and belong to one, and only one, user in D.

How can this be achieved? I have glanced at a few papers surrounding this issue, but they tend to get very technical very quickly.

Answer 1

I think what you want is a ring signature. This is a signature mechanism that allow you to prove someone signed within a set of actor without revealing which one.

You may want to read https://link.springer.com/chapter/10.1007%2F3-540-45682-1_32 and https://github.com/Blockstream/borromean_paper/raw/master/borromean_draft_0.01_34241bb.pdf

Answer 2

A public key will be considered authorised if belongs to a user in a database of verified users D. The problem is that it should not be possible for the verifier to ever link a public key to a specific authorised user.

Public key well may also be considered authorized if it is signed. With a blind signing scheme, it would be unfeasible to link a signature to the protocol instance (whom it was issued to).

RSA blind scheme introduced by Chaum is well known. "Rethinking PKI" book by Brands is relevant.