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.
Am I correctly understanding that I'd get the credential from say my state DMV once, and then later whenever I want to prove my age to a website the proof protocol is just between that website and my device? The DMV gets no information about what websites I use the DMV credential with and they get no information about when I use the credential even if the website and the DMV decide to cooperate? All they would be able to get was that at time T someone used a credential on the site that came from the DMV?
I tried to sketch out a design an age verification system, but it involved the DMV in each verification, which made timing attacks a problem. Briefly the website would issue a token, you'd get a blind signature of the token from the DMV's "this person is 18+" service, and return the token and unblinded signature to the website. I think that can be made to work but if the site and DMV cooperated they would likely be able to unmask many anonymous site users by comparing timing.
Getting the DMV out of the picture once your device is set up with the credential from them nicely eliminates that problem.
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 DMV gets no information about what websites I use the DMV credential with and they get no information about when I use the credential even if the website and the DMV decide to cooperate?
> 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.
Well, no. This is true only if you trust the unverifiable wallet software on your phone, which was provided by a for-profit, American big tech advertising company. In this protocol, the wallet may secretly leak the transaction details back to the DMV or whoever else they wish[1].
MatteoFrigo is suggesting that unlinkability requires ZKPs.
Your observation that a bad wallet could compromise unlinkability is not a refutation of that. To refute it you need to show that it is possible to achieve unlinkability without using a ZKP.
One part that I don't understand yet: How does the system ensure "sybil resistance"? (not sure if that's the right term in that context)
By providing both attestation of individual attributes combined with "unlikability", how would even a single verifying party ensure that different attestations don't come from the same identity?
E.g. In the case of age attestation a single willing dissenting identity could set up a system to mint attestations for anyone without it being traceable back to them, right? Similar to how a single of-age person could purchase beer for all their under age friends (+ without any feat of repercussions.
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.
That seems a bit like a game of whack-a-mole where as long as the forging side is willing to go further and further into out-of-hardware emulation (e.g. prosthetic finger on a robot hand to trick fingerprint scanners), they are bound to win. Biometrics don't feel like they hold up much if you can have collusion without fear of accountability.
> Our ZKP library at least makes the privacy end possible.
Yes, that's also one of the main things that make me excited about it. I've been following the space for quite some time now, and I'm happy that it becomes more tractable for standard cryptographic primitives and thus a lot more use-cases.
Thanks for your contributions to the space and being so responsive in this thread!
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.
Well, we can split up the credential into multiple ones sharing a serial number to fix the array signing. To bind to NIST there are some solutions based on ZkAttest (which got fixed, I made a few mistakes in it) to show signature under ECDSA while hiding it.
I disagree that no one is talking about it: the solutions are there, it is a question of getting the resources to put it together. Circuit based solutions have some nice properties, but the actual security assumptions are a bit odd, and the reasons people should trust a complex circuit and verification protocol are a bit hard.
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.
> 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
I'm not sure sumcheck and MPC in the head are that easy for undergraduates. By contrast cup products are pretty standard in topology and that's where the pairing comes from.
No. Using the MDOC requires a signature from a hardware security key in the phone, and a lot of the complexity is how to avoid leaking the private key, which would identify you.
An alternative would be some secure chip in a credit-card size plastic document, but nobody seems to like that idea. We (Google) don't make these choices.
Another approach could be for a component in the protocol that I do trust (eg an open source web browser) to serve as an intermediary, providing only the information required to each of the components that I don't trust (wallet, website). The wallet does not need to know who is requesting the proof, right?
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.
Yeah, Passkeys are doing the same thing, expecting users to just blindly trust American Big Tech companies. It's distressing that no one working on these protocols considers the developers of the software that implements the protocol to be a party in the protocol. What are the wallet provider's interests in this exchange? How can the user be protected from the wallet provider? Seems no one asks these questions :(
Anyone can implement passkeys. The feature where passkeys can be made to attest to the hardware provider is optional and no site I've used requires it. Firefox defaults to not allowing passkeys to attest to the hardware unless you click through a permission dialog.
I don't want to get into a Passkey derail, but no. The Passkey spec requires clients to handle the user's own data in certain ways, and the Passkey spec authors threaten clients that allow users to manage their own data with client bans.
The specifics depend on local regulations, but roughy speaking: the government gives you a document in a standard format (eg MDOC). Your phone stores the document, with cooperation from a secure element that binds the document to the phone. The website you visit verifies the proof. The government gives documents to whatever wallet they want, which may be a special government wallet. They may or may not give the document to Google Wallet.
> Your phone stores the document, with cooperation from a secure element that binds the document to the phone. The website you visit verifies the proof.
So it does require a "blessed" implementation, and I have to trust Google or Apple to handle my data? I cannot own the document myself and use an open-source client that I trust to provide the proof?
It depends on local regulations. As far as I can tell Europe will require some sort of blessing of the wallet. To be clear, governments will develop their own apps and it's not clear that Google will be blessed. We (Google) are giving them the code pro bono to improve privacy.
Hmm. This introduces a third party to the protocol, right? Specifically the developer of the wallet. So we now have three parties: the user, the wallet developer, and the relying party. Does this zk protocol protect the user's privacy from the wallet developer as well as the relying party?
In other words, does the protocol give the wallet access to information about the relying party? For example, could this wallet that I don't control tell its owner, or the government, that I am using it to access a certain website?
Yes, a malicious wallet could leak your information. This is why some governments will insist on using only blessed wallets. However, wallet+zk is strictly better than sending the plaintext MDOC to the relying party.
There are no solutions in this space, only tradeoffs, and elected representatives have picked one tradeoff.
That's too bad :( I wish the protocol had been designed with that in mind. Requiring users to trust proprietary software from Google & Apple to be in complete control over their digital identities is a pretty crummy direction to go in.
> Controlled by users: The EU Digital Identity Wallets will enable people to choose and keep track of their identity, data and certificates which they share with third parties. Anything which is not necessary to share will not be shared.
I think where the ZKP stuff being discussed here fails to meet this criteria is the wallet provider is also a third (non-user) party. You stated elsewhere that a malicious wallet could leak data about a transaction: that's exactly the vulnerability that is not being accounted for by this protocol.
> If you think you have a better idea shoot me an email.
Sure, will do. It does seem to me like a solvable problem. I think this kind of tech is really important and I'd love to see this hole get closed so I can feel better about supporting it.
Update: After some email discussion with Matteo, it looks like my fears are unfounded. The EU regulations seem to require wallets to be open source[1]. Assuming that wallets do not need to pass any sensitive transaction data down to the OS libraries, then it should be possible for users to verify the behavior of their wallet software by examining the source and possibly even by building & deploying it themselves.
In principle, you could use an open source implementation, but not a user-modifiable implementation.
Nothing stops a government from making their code open source and providing you with reproducible builds. You just won't be able to change the code to do something the government doesn't deem legal.
The post does not present a solution to that problem. Governments around the world, especially in Europe, have legislated the solution, and the solution they have picked is a privacy nightmare. This post solves the privacy problem, which is strictly better than the status quo. We (Google) do not decide what should or should not be regulated.
The context is the US mobile drivers licenses and the forthcoming digital identity documents in the EU. The government gives you an electronic document stored in your device, and now the problem is, why would you ever want to give a copy of your document to a third party.
This code solves the problem via zero-knowledge presentations of the document. This is real stuff already integrated in Google Wallet, not vaporware. See also the paper linked from GitHub.
Ignore the marketing in TFA.
The paper linked from Github is at [1]. Section 6.1 gives a fairly practical example of use with a passport, while 6.2 talks about how it might be used with a drivers license.
How do you prevent kids just obtaining a copy of such electronic document from somewhere? The actual document itself doesn't prove anything about your age; it just proves that you have the document.
To say this has nothing to do with blockchain is like saying RADAR had nothing to do with war. Yes, people knew Maxwell's equations prior, i.e. "knew the proofs," w.r.t. ZKP but it has only really been developed much later, during the war.
The whole field of zero-knowledge mathematics was, if not non-existent, but certainly marginalised, before the crypto investment has hit the scene; this is facts. Yes, Shamir et al. go back to 90s, but it's a far-cry from zkSNARK, zkVM stuff we have nowadays. It has also popularized many applications, like provable auctions (see kyber[1] library in Go as nice starting point...) and opened the door to homomorphic stuff.
The comment didn't say that ZKP had nothing to do with blockchain. The comment said that blockchains are not needed/involved for a zero knowledge proof, just like war is not needed for radar.
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.
That’s not accurate; all the industrial interest in ZKPs came from academic research. Yes, after the initial deployments the blockchain folks invested a shit-ton of money and greatly accelerated the available implementations (along with also contributing some new schemes), but it’s not like academic research was in some kind of stone-age beforehand.
Speaking as one of the implementors of the ZKP system described in the article.
The identity document (e.g. driver's license) is granted by an issuer (e.g. department of motor vehicles) and stored in the user's device only. Google is not part of this flow and the document is not sent to Google or stored by Google.
In fact, one major technical problem is how to make sure that the document cannot be used without having possession of the phone. To this end, the document is associated with the phone's secure element (think of a hardware yubikey already present in the phone itself) and cannot be used without the secure element.
Think of the document as a dictionary { "name": "foo", "address": "bar" ... }, although the reality is more complicated. One standard for these documents is ISO/IEC 18013-5, but other possibilities exist.
The proof itself proves the truth of a certain predicate on the document. The predicate is something like "The document parses correctly, it is bound to the device's secure element, and it contains zip_code = 012345".
The phone generates the proof at presentation time in about 1s. Another major technical difficulty is that past attempts at solving this problem required prover time of tens of seconds. Our proofs have the property that no entity, including a future quantum computer, can learn anything from the proof other than the predicate is true. See https://eprint.iacr.org/2024/2010 for the gory details. The specific predicate being proved is in Algorithm 10.
When you say "interactive" you probably mean "at presentation time", as opposed to "in advance". We generate a fresh proof at presentation time and not in advance. Be aware that the ZKP literature uses "interactive" in a different sense, in which the verifier keeps posing multiple challenges to the prover until the verifier is satisfied that the proof is correct. Our system is derived from an "interactive" protocol in this technical sense, and transformed into a "non-interactive" prover via a general transformation called "Fiat-Shamir". The net effect is that the verifier asks "tell me your age and nothing else", the prover sends one message with the proof, and that's it.
I could not find a description of your algorithm, which makes it hard to give you feedback. However, here are a few questions that come to my mind from a cryptography/ZK perspective.
1) elliptic-curve cryptography cares about 256-bit multiplication (and perhaps 384 or 521 bits for the truly paranoid). Is your algorithm better than alternatives in that regime?
2) cryptography/ZK cares about multiplication mod p, and not about multiplication per se. Of course you can perform the multiplication and then reduce mod p, but other techniques exist (e.g. Montgomery multiplication) that interleave the multiplication and the reduction for better performance. It is hard to combine Montgomery and Karatsuba. Can your technique be combined with Montgomery?
3) ZK also cares about binary fields GF(2^k). Does your technique work in those fields?
1) Is your algorithm better than alternatives for 256-bit multiplication (or 384/521 bits)?
Yes.
RPF consistently outperforms Karatsuba and other classic methods (including Toom-Cook and even some FFTs) in the 128–800 digit (approx. 400–2600 bit) range.
Specifically, at 256, 384, and 521 bits, which are critical for elliptic curve cryptography,
RPF is faster in squaring — both in raw integer mode and when enhanced with GMP.
We observed:
Lower execution times than Karatsuba starting from 150–180 bits onward.
Better scaling, meaning performance advantage widens as bit size increases.
2) Can your technique be combined with Montgomery multiplication?
Yes, and this is one of RPF’s strong points.
Karatsuba and Montgomery are hard to combine efficiently due to their recursive and carry-heavy nature.
RPF, however, has a more linear and structured squaring layout, making it much easier to wrap inside Montgomery’s reduction loop.
In initial tests, we were able to:
Integrate RPF inside a Montgomery-style multiplication framework with minimal change.
Maintain a performance lead compared to Karatsuba-integrated approaches.
We’re exploring even more optimized coupling with Montgomery reductions for modular cryptography applications.
3) Does your technique work in binary fields GF(2^k)?
RPF can be adapted to binary fields.
Since GF(2^k) squaring operations have specific bit-level behaviors (like lack of carry propagation), the base version of RPF designed for integers won’t directly transfer.
However, we are working on a variant of RPF optimized for GF(2^k) that leverages:
XOR-style operations instead of additions,
and efficient bit-splitting to emulate RPF’s structure in binary logic.
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.