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

[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