Re: Anonymous Credentials from ECDSA - (Google, Dec. 2024)

Yes, thanks all!

This is exciting work at the frontier! I’ll be actively taking the pulse on identity and credentialing at ETHDenver<https://www.ethdenver.com> this year, and happy to connect with anyone who might be attending (it’s free!).

Here’s a rather expansive side event list<https://docs.google.com/spreadsheets/d/1SWrgxh1W0GrVhbvchZzhGc4Be0z-fB-vqsbVjLinXW0/edit?usp=sharing> (ctrl+f ‘zk’) for those who, like me, prefer good old fashion spreadsheets :)

Best,
Taylor
________________________________
From: Kim Hamilton <kimdhamilton@gmail.com>
Sent: Monday, February 10, 2025 8:41 PM
To: Matteo Frigo <matteof@google.com>
Cc: public-credentials@w3.org <public-credentials@w3.org>; Zoey 0x <zoey@pse.dev>
Subject: Re: Anonymous Credentials from ECDSA - (Google, Dec. 2024)

Thank you Matteo and Andrea for this interesting discussion.


At DIF, we’re interested in encouraging adoption of solutions of this form; informally, “ZKP wrapping” existing credentials.  As Matteo notes, this enhances privacy without requiring upgrades to issuer systems.

Since the trust model differs from that of the usual 3‐party model, we're focused on elaborating the trust model and potential use cases. I'd appreciate any feedback on our early draft<https://github.com/decentralized-identity/zkp-self-attestations/blob/main/trust_models/general_trust_model.md>.  (Draft of use cases to follow.)

This work item was inspired by PSE's Anon Aadhaar<https://github.com/anon-aadhaar/anon-aadhaar> and OpenPassport<https://www.openpassport.app/>.  It's exciting to see such active development in this area!

Thanks,
Kim






Sent via Superhuman<https://sprh.mn/?vip=kimdhamilton@gmail.com>


On Sun, Feb 09, 2025 at 3:05 PM, Matteo Frigo <matteof@google.com<mailto:matteof@google.com>> wrote:
[I don't normally read this mailing list and I am replying from the web interface.
I hope this email is informative and not spam]

Thanks Andrea for your kind words about our work.

There is some literature about this approach, usually under the general umbrella of "SNARK" or zk-SNARK.
Also look for STARK and the Starkware company.  Many people are working on this topic in the context of blockchain,
and there are people even crazier than us producing zero-knowledge proofs of the execution of a simulated processor,
e.g. Ethereum EVM or even the risc-v architecture.

As you have surmised, our work has been motivated by practical uses, and it had the well-defined goal
of producing zero-knowledge proofs for ISO MDOC documents (we did MDOC first for arbitrary reasons, we are aware
that SD-JWT exists, but didn't attack it yet).  While the blockchain setup optimizes for proof size and verifier time,
we are optimizing for prover time because the prover runs on a mobile device.

There are previous attempts to use generic ZK technology to avoid touching the existing credentials infrastructure,
including the Cinderella and the C0C0 system that we reference in the paper.  These systems ended up being too slow (minutes)
for the applications we have in mind.  So one way to look at our paper is what's the minimum amount
of hacks and complications that one must introduce in order to run in reasonable time.

A different approach to the same problem was taken recently in https://eprint.iacr.org/2024/2013
who figured out a clever way to re-randomize a proof quickly, so one can spend more time in advance to
produce the proof.  While we like that approach, that system requires a "trusted setup" of perhaps 1GB
of semi-random numbers, which is not really suited for a mobile device.

We are also great fans of the Binius system of Diamond and Posen.  While it appears that today
Binius is slower than our system for our specific use case (which is not a surprise given that we
optimized for our use case and Binius did not), it is entirely possible that Binius may turn out to
be competitive or better given enough effort.

Finally, I'd like to clear one technical misconception in your email.  Reed-Solomon encoding is used not for robustness, but
for soundness.  Ligero works by assuming that the private inputs are the evaluations of a low-degree polynomial at certain points,
and the verifier is allowed to ask for the evaluations of the same polynomial at different points chosen randomly by the verifier.
With the right parameters and other subtleties, the verifier catches any cheating attempt from the prover with overwhelming probability.
Polynomial interpolation is exactly what Reed-Solomon codes do.  Thus, Reed-Solomon is not used for ensuring message integrity
over the network, but it is an integral part of the security properties of the system.

Cheers,
Matteo Frigo