3 ms·

The party to hold a gov id - site id mapping would be you. The rest can then be facilitated using zero-knowledge proofs, I believe. I'm not super well-versed i

The party to hold a gov id - site id mapping would be you. The rest can then be facilitated using zero-knowledge proofs, I believe. I'm not super well-versed in crypto though, so I confess this is a lot more conjecture than knowledge.

fluoridation 1y ago
So the user generates the ID for each site he visits? What prevents them from generating arbitrary IDs? The only way I can imagine this working is: 1. You go to the government and request to have a digital ID generated. 2. The government generates a random number. 3. The government issues a request to an NGO to generate a new cryptographic object based on the random number, and receives back a retrieval number. 4. The government gives you the retrieval number, which you can use to get your digital ID from the NGO. This way, the government only has the mapping between your identity and a random number, and the NGO only has the mapping between the random number and the generated object, with no possibility to deanonymize it because you don't present any ID to get it. Obviously, there must be no information exchange between the government and the NGO.
- perching_aix 1y ago
  > 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.
  - fluoridation 1y ago
    >The expectation is that you would have only one valid secret_key at any time Why, though? If you're the only one who knows it, nothing prevents you from creating as many identities for the same site as you wish.
    - perching_aix 1y ago
      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.
      - hellojesus 1y ago
        How sad a world we'd live in where the government has to bless you in order to be able to use the web.

fluoridation 1y ago

So the user generates the ID for each site he visits? What prevents them from generating arbitrary IDs? The only way I can imagine this working is: 1. You go to the government and request to have a digital ID generated. 2. The government generates a random number. 3. The government issues a request to an NGO to generate a new cryptographic object based on the random number, and receives back a retrieval number. 4. The government gives you the retrieval number, which you can use to get your digital ID from the NGO. This way, the government only has the mapping between your identity and a random number, and the NGO only has the mapping between the random number and the generated object, with no possibility to deanonymize it because you don't present any ID to get it. Obviously, there must be no information exchange between the government and the NGO.

perching_aix 1y ago
> 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.
- fluoridation 1y ago
  >The expectation is that you would have only one valid secret_key at any time Why, though? If you're the only one who knows it, nothing prevents you from creating as many identities for the same site as you wish.
  - perching_aix 1y ago
    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.
    - hellojesus 1y ago
      How sad a world we'd live in where the government has to bless you in order to be able to use the web.