5 ms·

This is, of course, very technical, but here is how it works at a high level. In the non-ZKP presentation, the "holder" (phone) sends the credential to the rel

This is, of course, very technical, but here is how it works at a high level. In the non-ZKP presentation, the "holder" (phone) sends the credential to the relying party (website), and the RP executes some verification algorithm. In the ZK presentation, the holder executes the verification algorithm and sends to the RP a proof that the algorithm was executed correctly. The "proof" has this magical property that it reveals nothing other than the check passed. (You will have to take on faith that such proofs exist.) In particular, if the check was the predicate "I have a signature by ISSUER on HASH, and SHA256(DOCUMENT)==HASH, and DOCUMENT["age_gt_18"]=TRUE", anybody looking at the proof cannot infer ISSUER, HASH, DOCUMENT, or HASH, or nothing else really. "Cannot infer" means that the proof is some random object and all HASH, DOCUMENT, ISSUER, etc. that satisfy the predicate are equally likely, assuming that the randomness used in the proof is private to the holder. Moreover, a generating a proof uses fresh randomness each time, so given two proofs of the same statement, you still cannot tell whether they come from the same ISSUER, HASH, DOCUMENT, ...

parineum 10mo ago
If it's not linked to an identity, why can't a kid use a parent's key?
- MatteoFrigo 10mo ago
  Excellent question. More generally, what prevents me from copying the credential and giving it to somebody else? The currently favored approach works like this. The DOCUMENT contains a device public key DPK. The corresponding secret key is stored in some secure hardware on the phone, designed so that I (or malware or whatever) cannot extract the secret key from the secure hardware. Think of it as a yubikey or something, but embedded in the phone. Every presentation flow will demand that the secure element produce a signature of a random challenge from the RP under the secret key of the secure hardware. In the ZKP presentation, the ZKP prover produces a proof that this signature verifies correctly, without disclosing the secret key of the secure hardware. In your example, the parent could give the phone to the kid. However, in current incarnations, the secure hardware refuses to generate a signature unless unlocked by some kind of biometric identification, e.g. fingerprint. The fingerprint never leaves the secure hardware. How does the issuer (e.g. the republic of France) know that DOCUMENT is bound to a given fingerprint? This is still under discussion, but as a first bid, a French citizen goes to city hall with his phone and obtains DOCUMENT after producing a fingerprint on the citizen's phone (as opposed to a device belonging to the republic of France). You can imagine other mechanisms based on physical tokens (yubikeys or embedded chips in credit cards, or whatever). Other proposals involve taking pictures compared against a picture stored in DOCUMENT. As always, one needs to be clear about the threat model. In all these proposals the biometric identification unlocks the secure hardware into signing a nonce. The biometrics themselves are not part of the proof and are not sent to the relying party or to the issuer.
  - parineum 10mo ago
    So adults are required to own a phone to prove their age? Can I log into an age gated service at a library without a phone?
    - MatteoFrigo 10mo ago
      Another excellent question. The current answer in the EU seems to be "you need a phone". My preferred answer (despite being one of the Google guys who designed the ZKP mechanism) would be that the government sends you some sort of plastic card with a chip that does not tie you to a phone. Still fighting that battle.
      - parineum 10mo ago
        Thanks for answering, I appreciate it.
      - fsflover 10mo ago
        I guess owning some computer should be fine as a requirement? It just should not be tied to the US megacorps. A web app perhaps?
        MatteoFrigo 10mo ago
        Yes. However, at some point there needs to be some unforgeable piece of hardware that prevents copying the document. I am a big fan of yubikeys and I wish everybody used them, but the reality is that people lose them way more often than they lose their phone.
  - donmcronald 10mo ago
    > How does the issuer (e.g. the republic of France) know that DOCUMENT is bound to a given fingerprint? This is still under discussion, but as a first bid, a French citizen goes to city hall with his phone and obtains DOCUMENT after producing a fingerprint on the citizen's phone (as opposed to a device belonging to the republic of France). Are you saying that someone goes to city hall, shows ID, and gets a DOCUMENT that certifies age, but doesn't link back to the person's identity? And it's married to a fingerprint in front of the person checking ID? Is there a limit on how many times someone can get a DOCUMENT? If not, it'll become a new variation of fake id and eventually there's going to be an effort to crack down on misuse. If yes, what happens if I get unlucky and lose / break my phone limit + 1 times? Do I get locked out of the world? The only way I can imagine limiting abuse and collateral damage at the same time is to link an identity to a DOCUMENT somehow which makes the whole ZKP thing moot. I'd be more worried about the politics though. There's no way any government on the planet is going to keep a system like that limited to simple age verification. Eventually there's going to be enough pretense to expand the system and block "non-compliant" sites. Why not use the same DOCUMENT to prove age to buy beer? Sanity for guns? Loyalty for food? What happens if the proof gets flipped to run the other direction and a DOCUMENT is needed to prove you're a certified journalist? Any sources without certification can be blocked and the ZKP aspect doesn't matter at that point because getting the DOCUMENT will be risky if you're a dissenter. Maybe there's an interview. Maybe there's a background check. Has your phone ever shown up near a protest? It's just like the Android announcement that developers need to identify themselves to distribute apps, even via side loading. The ultimate goal is to force anyone publishing content to identify themselves because then it's possible to use the government and legal system to crush dissenting views. Big tech caused most of the problems and now they're going to provide the solution with more technology, more cost, and less freedom which is basically what they've been doing for the last 2 decades so it's not a surprise.
- jolmg 10mo ago
  I think a parent should be able to give their kid access if they deem their kid mature enough. If the kid can handle social media without it becoming an addiction or a self-esteem issue or similar, then it would generally be a net positive. For example, social media may include YouTube which has a lot of educational content. Why hold the kid back?
pksebben 10mo ago
the more I think about it, the more I feel like I need someone with deep knowledge to explain ZKPs to me. So like, we've got this algorithm that gets sent our way and we run it and that provides kind of a cryptographic hash or whatever. But if we're running the algorithm ourselves what's to stop us from lying? Where does the 'proof' come from? What's the check that it's running and why do we inherently trust the source it's checking?
- MatteoFrigo 10mo ago
  I am someone with "deep knowledge", but HN is not the proper place for this discussion. See https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.html https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.htm... for the gory details. Here is a hopefully simple example of how this ZKP thing may even be possible. Imagine that you give me a Sudoku puzzle. I solve it, and then I want to prove to you that I have solved it without telling you the solution. It sounds impossible, but here is one way to do it. I compute the solution. I randomly scramble the digits 1-9 and I put the scrambled solution in a 9x9 array of lock boxes on a table. I have the keys to the 81 locks but I am not giving you the key yet. You randomly ask me to open either 1) one random row chosen by you; 2) one random column chosen by you; 3) one random 3x3 block chosen by you; or 4) the cells corresponding to the original puzzle you posed to me. In total you have 28 possibilities, and assume that you choose them with equal probability. You tell me what you want and I open the corresponding lockboxes. You verify that the opened lock boxes are consistent with me knowing a solution, e.g. all numbers in a row are distinct, the 3x3 block consists of distinct numbers, etc. If I am cheating, then at least one of your 28 choices will be inconsistent, and you catch me with probability 1/28, so if we repeat this game 1000 times, and I don't know the solution, you will catch me with probability at least 1-(1/28)^1000 which is effectively 1. However, every time we repeat the game, I pick a different random scrambling of the integers 1-9, so you don't learn anything about the solution. All of ZKP is a fancy way to 1) encode arbitrary computations in this sort of protocol, and 2) amplify the probability of success via clever error-correction tricks. The other thing you need to know is that the protocol I described requires interaction (I lock the boxes and you tell me which ones to open), but there is a way to remove the interaction. Observe that in the Sudoku game above, all you are doing is flipping random coins and sending them to me. Of course you cannot let me pick the random coins, but if we agree that the random coins are just the SHA256 hash of what I told you, or something else similarly unpredictable, then you will be convinced of the proof even if the "coins" are something that I compute myself by using SHA256. This is called the "Fiat-Shamir transformation". How do we implement the lock boxes? I tell you SHA256(NONCE, VALUE) where the NONCE is chosen by me. Given the hash you cannot compute VALUE. To open the lock box, I tell you NONCE and VALUE, which you believe under the assumption that I cannot find a collision in SHA256.

parineum 10mo ago

If it's not linked to an identity, why can't a kid use a parent's key?

MatteoFrigo 10mo ago
Excellent question. More generally, what prevents me from copying the credential and giving it to somebody else? The currently favored approach works like this. The DOCUMENT contains a device public key DPK. The corresponding secret key is stored in some secure hardware on the phone, designed so that I (or malware or whatever) cannot extract the secret key from the secure hardware. Think of it as a yubikey or something, but embedded in the phone. Every presentation flow will demand that the secure element produce a signature of a random challenge from the RP under the secret key of the secure hardware. In the ZKP presentation, the ZKP prover produces a proof that this signature verifies correctly, without disclosing the secret key of the secure hardware. In your example, the parent could give the phone to the kid. However, in current incarnations, the secure hardware refuses to generate a signature unless unlocked by some kind of biometric identification, e.g. fingerprint. The fingerprint never leaves the secure hardware. How does the issuer (e.g. the republic of France) know that DOCUMENT is bound to a given fingerprint? This is still under discussion, but as a first bid, a French citizen goes to city hall with his phone and obtains DOCUMENT after producing a fingerprint on the citizen's phone (as opposed to a device belonging to the republic of France). You can imagine other mechanisms based on physical tokens (yubikeys or embedded chips in credit cards, or whatever). Other proposals involve taking pictures compared against a picture stored in DOCUMENT. As always, one needs to be clear about the threat model. In all these proposals the biometric identification unlocks the secure hardware into signing a nonce. The biometrics themselves are not part of the proof and are not sent to the relying party or to the issuer.
- parineum 10mo ago
  So adults are required to own a phone to prove their age? Can I log into an age gated service at a library without a phone?
  - MatteoFrigo 10mo ago
    Another excellent question. The current answer in the EU seems to be "you need a phone". My preferred answer (despite being one of the Google guys who designed the ZKP mechanism) would be that the government sends you some sort of plastic card with a chip that does not tie you to a phone. Still fighting that battle.
    - parineum 10mo ago
      Thanks for answering, I appreciate it.
    - fsflover 10mo ago
      I guess owning some computer should be fine as a requirement? It just should not be tied to the US megacorps. A web app perhaps?
      - MatteoFrigo 10mo ago
        Yes. However, at some point there needs to be some unforgeable piece of hardware that prevents copying the document. I am a big fan of yubikeys and I wish everybody used them, but the reality is that people lose them way more often than they lose their phone.
- donmcronald 10mo ago
  > How does the issuer (e.g. the republic of France) know that DOCUMENT is bound to a given fingerprint? This is still under discussion, but as a first bid, a French citizen goes to city hall with his phone and obtains DOCUMENT after producing a fingerprint on the citizen's phone (as opposed to a device belonging to the republic of France). Are you saying that someone goes to city hall, shows ID, and gets a DOCUMENT that certifies age, but doesn't link back to the person's identity? And it's married to a fingerprint in front of the person checking ID? Is there a limit on how many times someone can get a DOCUMENT? If not, it'll become a new variation of fake id and eventually there's going to be an effort to crack down on misuse. If yes, what happens if I get unlucky and lose / break my phone limit + 1 times? Do I get locked out of the world? The only way I can imagine limiting abuse and collateral damage at the same time is to link an identity to a DOCUMENT somehow which makes the whole ZKP thing moot. I'd be more worried about the politics though. There's no way any government on the planet is going to keep a system like that limited to simple age verification. Eventually there's going to be enough pretense to expand the system and block "non-compliant" sites. Why not use the same DOCUMENT to prove age to buy beer? Sanity for guns? Loyalty for food? What happens if the proof gets flipped to run the other direction and a DOCUMENT is needed to prove you're a certified journalist? Any sources without certification can be blocked and the ZKP aspect doesn't matter at that point because getting the DOCUMENT will be risky if you're a dissenter. Maybe there's an interview. Maybe there's a background check. Has your phone ever shown up near a protest? It's just like the Android announcement that developers need to identify themselves to distribute apps, even via side loading. The ultimate goal is to force anyone publishing content to identify themselves because then it's possible to use the government and legal system to crush dissenting views. Big tech caused most of the problems and now they're going to provide the solution with more technology, more cost, and less freedom which is basically what they've been doing for the last 2 decades so it's not a surprise.
jolmg 10mo ago
I think a parent should be able to give their kid access if they deem their kid mature enough. If the kid can handle social media without it becoming an addiction or a self-esteem issue or similar, then it would generally be a net positive. For example, social media may include YouTube which has a lot of educational content. Why hold the kid back?

pksebben 10mo ago

the more I think about it, the more I feel like I need someone with deep knowledge to explain ZKPs to me. So like, we've got this algorithm that gets sent our way and we run it and that provides kind of a cryptographic hash or whatever. But if we're running the algorithm ourselves what's to stop us from lying? Where does the 'proof' come from? What's the check that it's running and why do we inherently trust the source it's checking?

MatteoFrigo 10mo ago
I am someone with "deep knowledge", but HN is not the proper place for this discussion. See https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.html https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.htm... for the gory details. Here is a hopefully simple example of how this ZKP thing may even be possible. Imagine that you give me a Sudoku puzzle. I solve it, and then I want to prove to you that I have solved it without telling you the solution. It sounds impossible, but here is one way to do it. I compute the solution. I randomly scramble the digits 1-9 and I put the scrambled solution in a 9x9 array of lock boxes on a table. I have the keys to the 81 locks but I am not giving you the key yet. You randomly ask me to open either 1) one random row chosen by you; 2) one random column chosen by you; 3) one random 3x3 block chosen by you; or 4) the cells corresponding to the original puzzle you posed to me. In total you have 28 possibilities, and assume that you choose them with equal probability. You tell me what you want and I open the corresponding lockboxes. You verify that the opened lock boxes are consistent with me knowing a solution, e.g. all numbers in a row are distinct, the 3x3 block consists of distinct numbers, etc. If I am cheating, then at least one of your 28 choices will be inconsistent, and you catch me with probability 1/28, so if we repeat this game 1000 times, and I don't know the solution, you will catch me with probability at least 1-(1/28)^1000 which is effectively 1. However, every time we repeat the game, I pick a different random scrambling of the integers 1-9, so you don't learn anything about the solution. All of ZKP is a fancy way to 1) encode arbitrary computations in this sort of protocol, and 2) amplify the probability of success via clever error-correction tricks. The other thing you need to know is that the protocol I described requires interaction (I lock the boxes and you tell me which ones to open), but there is a way to remove the interaction. Observe that in the Sudoku game above, all you are doing is flipping random coins and sending them to me. Of course you cannot let me pick the random coins, but if we agree that the random coins are just the SHA256 hash of what I told you, or something else similarly unpredictable, then you will be convinced of the proof even if the "coins" are something that I compute myself by using SHA256. This is called the "Fiat-Shamir transformation". How do we implement the lock boxes? I tell you SHA256(NONCE, VALUE) where the NONCE is chosen by me. Given the hash you cannot compute VALUE. To open the lock box, I tell you NONCE and VALUE, which you believe under the assumption that I cannot find a collision in SHA256.