# 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.