Zero Knowledge Police Check

I’m curious if there’s a zero-knowledge protocol for the following. Suppose a Passer-by is stopped by a Vigilante who has a list of wanted criminals. Can the Passer-by prove he has a valid ID and he’s not on the list without disclosing his identity?

Assume the ID is a bunch of data signed by an authority in some way, anticipating just such a situation (this authority values liberty very much). Vigilantes must do no better than chance to distinguish between non-wanted Passers-by after arbitrarily many rounds of the protocol.

It’s also interesting if this is possible without the Passer-by learning the contents of the list.

Yes, you can certainly construct this with zero-knowledge proofs of knowledge, some one-way function $$OW$$ (lets say bijective for simplicity), and a signature schemes $$\Sigma$$.

A simple protocol

• Citizens choose a random preimage $$x$$ of the one-way function. Their secret key is $$x$$, their public key is $$y = OW(x)$$.
• Citizens also store a state-issued signature $$\sigma$$ on $$y$$.
• You can prove arbitrary NP statements in zero-knowledge, i.e. statements of the form "I know $$a,b,c$$ such that [poly-time checkable statement about $$a,b,c$$]". So assume the citizen is approached with a list of $$y_1,\dots,y_n$$ of wanted criminals' public keys. Both parties can then set up a zero-knowledge proof in which the citizen proves

"I know $$x,y,\sigma$$ such that $$y = OW(x)$$, and $$\sigma$$ is a valid signature on $$y$$, and $$y\notin \{y_1,\dots,y_n\}$$".

Zero-knowledge guarantees that the vigilante does not learn the values of $$x,y,\sigma$$. The proof of knowledge property guarantees that the citizen can only make the vigilante accept if he actually knows $$x,y,\sigma$$ with these properties. This (kinda) prevents a person on the list from winning the proof - they need some honest/unlisted person's secret $$x$$ and their signature $$\sigma$$, which only the honest person knows.

Drawbacks

In practice, this simple scheme has limited applicability because wanted persons only need to convince any unlisted person to give them a copy of their $$x,\sigma$$. If they have that, they can easily pass the police check. The underlying problem is that while physical IDs are (ideally) hard to copy, a digital identity is just a bunch of bits that is easily duplicated and handed over to another person. You can probably make all of this more elaborate and give each person a trusted device that stores $$x,\sigma$$ in an unclonable way. But as soon as you have that, the zero-knowledge protocol becomes somewhat overkill - the police could just ask the trusted device whether it sees its identity on the list.

Hiding the list

In the scheme listed above, the list contains no identifying information about the listed people (just a random value). You can however recognize values you have already seen before (e.g., friends). You could hide the list, for example, as follows:

• Assume for concreteness that the one-way function maps an integer $$x$$ to $$OW(x) = g^x$$ for some fixed $$g$$ in some prime-order group $$\mathbb{G}$$ where decisional Diffie-Hellman is hard.
• The signature stuff stays the same and the list is comprised of the criminals' public keys $$g^{x_1},\dots,g^{x_n}$$.
• Before showing the list to the citizen, the vigilante now randomizes the list to look random:
• The vigilante chooses a random $$r\leftarrow\mathbb{Z}_p$$.
• He then hands $$h = g^r$$ and $$h^{x_1},\dots,h^{x_n}$$ to the citizen.
• Under the decisional Diffie-Hellman assumption, the elements $$h^{x_i}$$ are indistinguishable from random group elements. 
• The citizen can still prove in a zero-knowledge proof of knowledge that he knows $$x,y,\sigma$$ such that $$y = g^x$$, $$\sigma$$ is a signature on $$y$$, and $$h^x \notin \{h^{x_1},\dots h^{x_n}\}$$.

: of course, this only holds if the secret key $$x_i$$ of the entry is unknown to the citizen. Necessarily, each citizen must be able to recognize himself on the list. It's just all other entries that now look random.