> So the user generates the ID for each site he visits? What prevents them from generating arbitrary IDs?
The construction would go basically like this:
pseudonym = VRF(secret_key + site_id)
The expectation is that you would have only one valid secret_key at any time, and it would be unknown to the government. This kind of scheme is called anonymous credential generation in literature I believe. It can be established the secret_key got govt backed, but that's it.
The site_id would be e.g. domain cert public key or similar (domain ownership is a moving target, so just the domain name imo is not sound).
VRF is a verifiable random function. This is the magic ZK part.
Pseudonym is what you present to the site, i.e. the identity you go by.
This way the site can verify that this pseudonym was specifically issued for it (making it site unique), and that it belongs to a govt certified identity (of which there should be only one issued at a time per person). The VRF is deterministic, guaranteeing that it's the same person every time.
Revocation is annoying so I didn't bother thinking that through but should be fairly okay I think?
I believe this is robust to people forging arbitrary IDs, to sites colluding with each other in deanonymization, and colluding with the govt in the same. The only kickers I can think of are secret_key misuse (e.g. via duress) / theft / loss / sharing, and the trust anchor (the govt) being untrustworthy (forging invalid or duplicate identities). Would also need to handle people dying, but that would be pretty much just revocation.
I consider trust anchor issues out of scope. The remainder doesn't sound too bad to try defending for, and I think is also basically out of scope.
Potentially important edit: I'm not accounting for timing side channels here, which might be relevant during revocation or else.
Another: didn't mention but in my humble opinion cryptographically attesting people is unsound. People can't calculate crypto in their head, and can't recall long arbitrary strings of hex. What is appropriate to attest (if anything) is their devices instead. But that's a layer of complication I didn't want to deal with here.
It's an interactively generated thing, so the govt can ensure you can only complete it once, while being ignorant of its content. Or at least that's the claim of these protocols (e.g. Camenisch–Lysyanskaya (CL) signatures) afaik. I'm not sure how they work in detail.
The construction would go basically like this:
pseudonym = VRF(secret_key + site_id)
The expectation is that you would have only one valid secret_key at any time, and it would be unknown to the government. This kind of scheme is called anonymous credential generation in literature I believe. It can be established the secret_key got govt backed, but that's it.
The site_id would be e.g. domain cert public key or similar (domain ownership is a moving target, so just the domain name imo is not sound).
VRF is a verifiable random function. This is the magic ZK part.
Pseudonym is what you present to the site, i.e. the identity you go by.
This way the site can verify that this pseudonym was specifically issued for it (making it site unique), and that it belongs to a govt certified identity (of which there should be only one issued at a time per person). The VRF is deterministic, guaranteeing that it's the same person every time.
Revocation is annoying so I didn't bother thinking that through but should be fairly okay I think?
I believe this is robust to people forging arbitrary IDs, to sites colluding with each other in deanonymization, and colluding with the govt in the same. The only kickers I can think of are secret_key misuse (e.g. via duress) / theft / loss / sharing, and the trust anchor (the govt) being untrustworthy (forging invalid or duplicate identities). Would also need to handle people dying, but that would be pretty much just revocation.
I consider trust anchor issues out of scope. The remainder doesn't sound too bad to try defending for, and I think is also basically out of scope.
Potentially important edit: I'm not accounting for timing side channels here, which might be relevant during revocation or else.
Another: didn't mention but in my humble opinion cryptographically attesting people is unsound. People can't calculate crypto in their head, and can't recall long arbitrary strings of hex. What is appropriate to attest (if anything) is their devices instead. But that's a layer of complication I didn't want to deal with here.