MatteoFrigo

A true giant. His algorithm for Pythagorean addition, which computes sqrt(a^2 + b^2) without taking square roots, is a wonderful gem.

Fun anecdote about early Matlab. In the '80s, while in high school, I "acquired" the source code of an early version of matlab, similar to the one that you linked. An email from Cleve Moler in 1990 asked people not to distribute the code, so I didn't give it to anybody. In the late '90s I visited Cleve Moler at his Mathworks office, and he proudly showed the early Matlab running on DOS, remarking that he only had that binary but had lost the source code. So I gave it to him.

ZKP is integrated in Google Wallet and has been running in production for a few months. We (Google) released the ZKP library as open source last year (this is the library used in production).

Announcement: https://blog.google/innovation-and-ai/technology/safety-secu...

Library: https://github.com/google/longfellow-zk

Paper: https://eprint.iacr.org/2024/2010

Afterwards, folks from ISRG produced an independent implementation https://github.com/abetterinternet/zk-cred-longfellow with our blessing and occasional help. I don't know if the authors would call it "production ready" yet, but it is at least code complete, fast enough, and interoperable with ours.

Here is one way: https://eprint.iacr.org/2024/2010

Our (Google) implementation: https://github.com/google/longfellow-zk

An independent implementation by the Internet Security Research Group: https://github.com/abetterinternet/zk-cred-longfellow Still being developed but already interoperable with ours.

European age verification app: https://ageverification.dev/av-doc-technical-specification/d...

Yes. The whole trick is a delicate balance between 1) committing to enough information that uniquely pins down the solution, assuming that one can open all the lock boxes, and 2) not opening too many lock boxes so that the verifier does not learn the solution.

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.

This post is restricted to the context of the European Union and is intended to be factual.

The EU age verification app is intended to be a pilot to the EU Digital Identity Wallet (EUDIW), which EU law requires to be deployed everywhere in Europe by the end of 2026. (Thus your "worry" is in fact the explicit plan of record.)

The EUDIW will store more attributes than age. Think of it as a digital form of a passport (with name, address, etc.). The exact set of attributes is determined by local laws.

Thus, the DOCUMENT that you obtain is tied to you, and of course the state knows what is in the DOCUMENT since the state creates the document in the first place.

The state does not generate proofs. The phone generates proofs. Given a proof (and only the proof), nobody can associate the proof to the phone or to you.

Now I switch to less factual statements, which are still approximately correct.

Why would you trust the wallet software not to phone home to the state or us (Google)? The EUDIW regulations require that the wallet software be open source. However, states will only issue DOCUMENT to their own certified wallet software---you cannot just take the open source and recompile it, since the state won't issue DOCUMENT to your uncertified wallet. (Maybe your gym will issue a gym membership to your raspberry pi wallet, since it's not a big deal.)

The reason for this strictness is that the EUDIW is intended for official or semi-official uses. For example, you can open a bank account with it, or use it as ID to get a mortgage. The bank must by law accept DOCUMENT, the state guarantees that DOCUMENT is correct, and you get better privacy than handling over a piece of plastic that is then photocopied by who knows whom. This is the tradeoff of the current EU law. It would be inappropriate for this kind of official, passport-like documents to store attributes such as your profession (journalist or whatever), and nobody is talking about it.

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.

I am someone with "deep knowledge", but HN is not the proper place for this discussion. See 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.

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.

FWIW, not that it matters, the proper acronyms are EUDI (EU Digital Itentity) and EUDIW (EUDI Wallet). DIW is not used.

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

I don't dispute your general sentiment that the ZK terminology is abused. However, at least one serious attempt exists to deploy a real ZKP system.

Specifically, our system [1] is available as open source [2] and work is underway to implement it in the EU age verification app [3]. I understand that this thread is about the UK and not the EU, and I make no claims about the UK. The system is not theory, but it is already shipping in Google Wallet [4] and in the Open Wallet Foundation multipaz system [5].

[1] https://eprint.iacr.org/2024/2010

[2] https://github.com/google/longfellow-zk

[3] https://ageverification.dev/av-doc-technical-specification/d...

[4] https://blog.google/products/google-pay/google-wallet-age-id...

[5] https://github.com/openwallet-foundation/multipaz

See https://github.com/google/longfellow-zk

Great question. The current thinking, at least in high level-of-assurance situations, is this. The identity document is only usable in cooperation with a hardware security element. The relying party picks a random nonce and sends it to the device. The device signs the nonce using the SE, and either sends the signature back to the relying party (in the non-ZKP case), or produces a ZKP that the signature is correct. The SE requires some kind of biometric authentication to work, e.g. fingerprint. So you cannot set up a bot that mints attestations. (All this has nothing to do with ZKP and would work the same way without ZKP.)

In general there is a tradeoff between security and privacy, and different use cases will need to choose where they want to be on this spectrum. Our ZKP library at least makes the privacy end possible.

You got it. There are a few nuisances, e.g. the "theorem statement" must be hashed as well so that proving that name=Mickey has a different oracle than proving that name=Goofy, but your basic understanding is correct.

No. ZK has a technical definition I don't want to get into, but note that the described system is deterministic and it always produces the same proof for Alice on a given day, and the proof for a later day can be derived from the proof for an earlier day. So two proofs can be linked back to Alice, and thus the system is not ZK. You need some kind of randomness for ZK.

See https://github.com/eu-digital-identity-wallet/eudi-doc-archi... for a reference to the nuances on all these topics, at least in the context of the European Union. Other locales have different problems and different solutions.

If you think you have a better idea shoot me an email.

As the Google guy who did the system, I really don't want to engage in this discussion.

I'll just say that the b-systems solve a different problem, and for the problem solved by our system there is currently no other solution available.

We spoke with Ying Tong and her colleagues from the Ethereum foundation. They have a project investigating which ZK technology would be best for digital credentials, and they have ran a few benchmarks at https://hackmd.io/@clientsideproving/zkIDBenchmarks For reference, our implementation runs the benchmark in about 200ms on the same hardware. The ETHF folks have had access to our code for a while and they agree with this result, but they decided not to publish numbers until the Google code was open-sourced for all. Our system is thus about 10x faster than the closest contender for this problem.

I don't want to make any general claims about who is better than whom. Our system is designed for our problem, and it's not a surprise that another system designed for another problem would perform worse on our problem. We are big fans of the Binius system of Diamond and Posen at Irreducible, and there is a chance that Binius may eventually work better than our stuff. That's however not the case today.

You also have to be careful about which hardware to use. Our implementation is single-threaded no GPU because it has to run on all phones everywhere in the world. Whether or not one can do better on a high-end GPU is irrelevant to us.

Either way, "stale" is not a word I would use. The word I would use is "works today".

The government gives a signed document to natural persons, and the ZK system proves that the document is signed by the government. Bots don't have passports or driver's licenses.

How does the government guarantee that the natural person is such? Various jurisdictions will decide what's good enough, but as a strawman proposal, you go in person to city hall once and upload a document to your phone.

The problem that needs to be solved is, how can a government give you an identity document in a way that you cannot give the document to somebody else. Whether or not this problem needs to be solved is a political question, but it seems like the majority thinks that identity documents should be hard to forge, in the same way as dollar bills should be hard to forge. The only practical solution is to have some sort of hardware that the user cannot forge, and relying parties will insist that the document be bound to such hardware. So yes, the something else could be software, but nobody will accept signatures from an emulated TPM. I had in mind a government-issued yubikey that can be identified as such, or maybe a plastic card with embedded secure chip with the same functionality. See https://github.com/eu-digital-identity-wallet/eudi-doc-archi... for the current thinking at least in the EU.

I should also remark that the above is a western-centric perspective, whatever "West" means. For example, I heard the architect for a similar system already deployed in India remark that in his jurisdiction many households share one phone across many family members, and India chose to accept more possibility for fraud in exchange for wider usability by the population. In that context this choice looks like the correct solution.

You are correct. The property that the colluding website and DMV still cannot identify you is called "unlinkability" and as far as I can tell cannot be achieved without zero-knowledge proofs. See https://github.com/user-attachments/files/15904122/cryptogra... for a discussion on this issue.

However, the timing attack resurfaces once you allow the DMV to revoke credentials. Exactly how the revocation is done matters. We are actively pushing back against solutions that require the DMV to be contacted to verify that the credential has not been revoked at presentation time, but this is a very nuanced discussion with inevitable tradeoffs between privacy and security.

The credential ("driver's license") contains a public key whose secret key is stored securely in a hardware secure element. The standard assumption is that the SE is in the phone, but it could be a yubikey or similar device. In order to use the credential, you need the SE. So you cannot buy a phone from somebody and download a credential from somebody else. You can however buy a phone and the credential from somebody. As a mitigation, the SE only generates the signature when unlocked via a fingerprint or similar biometric input which must match the one that was provided at the time the credential was issued. Whether or not your attack works in this scenario depends on the details. For example, if you only obtain the credential in person at a local government office and provide a fingerprint at that time, it's not that easy to sell the phone and the credential afterwards.

> I don't however think this is really the big debate. Rather it's about ensuring SD-JWT and related non-private solutions do not get used. To the extent that this work helps show it's possible, and the tradeoffs are desirable, it's good

On that we all agree.

The role of the secure element is only to "bind" the credential to the device, so that if you copy the credential somewhere else then the credential is useless. Concretely, the secure element produces a ECDSA signature that must be presented together with the credential. This is the normal protocol without ZKP. Concretely, the SE is in the phone, but could be a yubikey or something else.

The ZKP library does not run on the secure element. It runs on the normal CPU and produces a proof that the ECDSA signature from the SE is valid (and that the ECDSA signature from the issuer is valid, and that the credential has not expired, and ...) If you crack the ZKP library, all you are doing is producing an incorrect proof that will not verify.

Actually I meant blockchain qua blockchain, that is, ledger and consensus. There is no ledger and consensus at all in this system.

If people want to redefine blockchain to mean zero-knowledge, and they want to redefine zero-knowledge to mean succinct as they all seem to have done, it's not my problem.

There is no blockchain here, period.

Jokes aside, I really believe that once all is said and done our system is way simpler than BBS.

How are you going to check the document expiration date in BBS? Yes I know about range proofs, I know about the quaternion norms and the four prime theorem and all that jazz. But nobody is talking about it.

How are you going to bind to a hardware secure element that only uses NIST primes? Yes, there is a very clever variant called BBS# which I believe works, but that's not simple either.

How are you going to deal with existing standard formats? 80% of our complexity is in this step. BBS most likely cannot do it at all. If we can change the format then a lot of my complexity disappears too.

How are you going to deal with the fact that BBS signs an array and not a set, and thus you are leaking the fact that "family_name" is attribute at array index 42? Are you going to leak the schema (which re-introduces tracking) or are you going to agree in advance, now and forever, on a schema? (Our system hides the schema and works on an arbitrary key/value dictionary, up to a maximum size.)

It's easy to say "simple" when one has not built the real thing.

I hear you. The main problem is how to prevent you from giving your document to somebody else, and things have converged on certified smartphone with security key plus biometrics.

On the contrary, any undergraduate can understand our solution. In contrast, I don't know anybody who can explain the bilinear pairing in BBS.