I wanted to survey some of the recent results regarding zero-knowledge proofs for legacy signature schemes like ECDSA.
The main motivation for such a primitive has been the EU’s recent push for privacy-forward identity systems. In both this EU regulation, and a recent tender offer to develop age-assurance solution, the EU has codified the need for ZK proofs about identity attributes.
While the crypto community has been tackling the problem of asserting identity attributes (e.g., age-over-18) for decades via the notion of anonymous credentials, deploying such anonymous credentials at scale will require a few critical new pieces. In my opinion, the only viable path is to develop ZK for legacy signature schemes like ECDSA.
Our work
My colleague Matteo Frigo and I recently posted a paper outlining a new way to make efficient ZK proofs of possession about ECDSA signatures. One notable result is that we can form such proofs in ~60ms of total compute (single-core), with a proof that is roughly 200kb.
We discuss many of the reasons we believe developing ZK for legacy crypto like ECDSA (instead of new crypto like BBS+) is the better path for deployment. In a nutshell, we believe it is easier for cryptographers to develop ZK for legacy ECDSA than for every identity issuer to throw out their old systems and buy new ones that support BBS.
This is particularly true for mobile devices with secure elements. The best practice for storing an identity credential is to have a portion of the credential reside in a secure element or enclave (this is referred to as device-binding). This technique makes it harder for an adversary to share or copy credentials between devices. Today’s secure elements that are deployed on IOS and Android phones only support RSA and ECDSA. After spending a bit of time at Google asking about this, my conclusion is that upgrading secure elements to support the pairing-friendly curves needed for BBS is a decade-long process that will also involve somebody paying billions of dollars (most likely you, the end customer).
Crescent credentials
About 3 days after we posted our work to eprint, Christian, Guru-Vamsi, and Greg at Microsoft published their work on a similar problem. Christian also has a blog post explaining their result.
They observe that it is possible to re-randomize" the Groth16-style of proofs that would otherwise take minutes to form. Although the initial Groth16 proof-generation for a zk proof of posession of an ECDSA signature on message $m$" takes 1m, once a single proof has been created, it can be re-randomized in 20ms. A major advantage of using Groth16 is that the proof size is currently the smallest known proof: only a few hundred bytes!
This is indeed an interesting observation and may have a role in some applications. However, in the case of identity protocols at scale, I see a few drawbacks to that approach.
The first drawback is that the Groth16 and related proof systems (which are incredibly succinct) require a huge trusted parameter setup to function. These trusted setups are often referred to as ``powers-of-tau" ceremonies because their aim is to produce a sequence, $g, g*\tau, g*\tau^2, g*\tau^3, \ldots$ that are millions of elements long such that no party knows the secret $\tau$. There is a continuous ceremony running to produce such strings with confidence, and I’ve done some previous research about how to make these ceremonies more efficient.
Despite the progress on tau-ceremonies, there are two fundamental problems with requiring trusted setup parameters for any identity system that works at scale: in my experience, it would be impossible to convince a government or a set of relying parties to trust a single setup parameter that is gigabytes long.
Second, and more importantly, large setup parameters are incredibly unwieldly to deploy at scale. As an example, in my recent work at Google, I’ve learned that adding even 1mb of extra code to the Google play services (gmscore) library is highly scrutinized. I can’t imagine the rolling laughter from the stewards of that library if they were asked to add a 1gb public parameter to support ZK proofs.
For that reason, we limited ourselves to only considering proof systems that have no trusted parameter setups. The cost for that is of course the proof size. Proofs in our system will require 100s of kb. Again, this is a costly scenario to consider, given that every identity protocol now requires thousands of network packets (whereas the Groth16 or Crescent-style proofs can fit into 1 network packet!).
Woo et al.
Anna Woo, a student at Michigan, and her co-authors published a paper that will appear at the 2025 IEEE Security & Privacy conference entitled “…”. Her independent results are interesting because they also recognize the problem with trusted parameters, and focus on developing novel ZK techniques for legacy signature schemes. Their paper uses an interesting idea about how to combine zk-SNARKs with sigma protocols for proving knowledge of discrete logarithm values.
While their proof system runs slower than ours for similar problems, they have a number of promising directions. I believe the slower proof is a result of their choice to use an R1CS formulation of a circuit (instead of the layered circuits that we use, and that sumcheck is proficient at processing).
Thanks to Matteo and others for reading a draft of this post and sharing comments.