Matteo Frigo

@GiacomoFenzi @GalArnon42 @danboneh Does the smoothness of the domain matter at all?

@GiacomoFenzi @GalArnon42 @danboneh Fascinating work, guys. Just for my own peace of mind, can you confirm: 1) there is no problem in the unique-decoding regime, and 2) the problem is "extension codes over small fields" and not "codes over extension fields". I.e., a code with proper distance over GF(2^128) is ok.

New work with @asanso! We present an attack against hash based SNARGs using small fields that reduces conjectured security by around 10 bits. Most hash-based systems using 31-bit (or smaller) base fields are affected. ia.cr/2025/2197

@ronrothblum @recmo @benediktbuenz @GiacomoFenzi Very nice. Is there any way to extend this to verifying O(10) quadratic constraints? Support for quadratic constraints is one reason why Ligero is attractive to us (Longfellow).

@recmo @benediktbuenz @GiacomoFenzi Yes, just need them to be MLE friendly for the verifier to be efficient (like in WHIR)

With the recent exciting flurry of excitement around proximity gaps, it's easy to forget what they’re actually used for - building polynomial commitment schemes (PCS), which are a key backbone of SNARKs. In this new work with the wonderful @benediktbuenz, @GiacomoFenzi and @kleptographic we construct a new PCS based on tensor codes and code-switching that is very close to optimal. ia.cr/2025/2065

@daryakaviani Cool! Have you tried running it on a phone? The reason why our (Longfellow) codebase is single-threaded is that it is meant to run on mobile devices.

📝Read our paper here! eprint.iacr.org/2025/2094.pdf 👩‍💻 Code will be released soon.

Here's how LLM providers (& anyone) should be doing age verification in 2025: Keep the ID private; prove "≥18" with ZK proofs. Our new paper with @srinathtv "🌟Vega: Low‑Latency Zero-Knowledge Proofs over Existing Credentials" makes this practical today. eprint.iacr.org/2025/2094

@ronrothblum @mvenkita @ligero_inc @abhvious All cryptography is an unproven conjecture. A while back, for business reasons unrelated to the present discussion, I fed boolean SAT problems with millions of variables to a SAT solver and I got answers back in minutes. After months of doing this I wouldn't bet that P <> NP.

@mvenkita @ligero_inc @abhvious Worth clarifying that Google's ZK implementation does rely on unproven conjectures (e.g Fiat-Shamir) but not on proximity gap conjectures...

There has been FUD around how the recent amazing proximity gaps results affect current implementations of ZK. STARKs and Ligero use proximity gap theorems. At @ligero_inc, we have *NOT* relied on any unproven conjectures on proximity gaps. Google's ZK implementation by @abhvious and @MatteoFrig60839 *DO NOT* rely on any unproven conjectures. Both us and the Google team provide the best possible security and are *NOT BROKEN* by any of the amazing recent results. Thank your for your attention!

@jimpo_potamus @radi_cojbasic Sorry to hear this, Jim. I am a big fan of your work, and I have learned a lot from you and from your papers. I am eager to see what you do next.

Irreducible's time has come to an end. Long story short, @radi_cojbasic and I ultimately came to the realization that we couldn't sustainably build the kind of deep tech business in ZK that motivated us.

@mvenkita The point is that people have optimized bignum multiplication for decades.

@mvenkita The other possibility I had in mind was "Kronecker substitution": convolution p(x)q(x) for polynomials with coefficients < 2^k can be computed with a single bignum multiplication p(r) q(r) where r=n * 2^(2k). Not clear whether this is better or worse than CRT.

1) On my M4, running the Ligetron speed test in Chrome, I get ~10K Poseidon hash calls and ~250 EdDSA verifications per second. Try it here: platform.ligetron.com/speedtest This translates to proving a transaction block in under a minute on an M4 browser if Ethereum used EdDSA and Poseidon. Here's how we plan to achieve real-time proving for ECDSA (over secp256k1) and KECCAK: 👇

@mvenkita Great! Are you taking the route of reducing interpolation to convolution, or do you have some other trick? Either way looking forward to the results.

3) (Signature Verification) The secp256k1 curve is notorious in that the prime is not FFT friendly, neither is p^2 or p^3 for any FFT tricks. How will we solve it? We are going to use a method from the 3rd-5th century math (en.wikipedia.org/wiki/Chinese_r…). Look for some benchmarks that we will release soon. If that matches our current performance on EdDSA, then this part is already in line with real-time proving. (Hash computations) KECCAK is best represented as a Boolean circuit. Ligetron can be instantiated on GF(2^n) field to leverage this representation. In fact, the recent Google implementation of Ligero leverages the GF(2^128) field to represent SHA computations (which is the bottleneck).

@nellycyberpro For the crazy parallel prefix circuits read the paper by Guy Blelloch that we cite.

@nellycyberpro For the crazy binomial coefficients manipulations read the book "Concrete Math" by Knuth and others, or the first chapter of Knuth's "The art of computer programming" volume 1.

I've been listening to @zeroknowledgefm's episode with @MatteoFrig60839 & Abhi from Google, where they discuss bringing ZK to Google Wallet and their paper, "Anonymous Credentials from ECDSA." It's a great episode, and I'm learning a lot. 🧵

@nellycyberpro Can you elaborate a bit more on your current level of understanding? Specifically, which of the following terms make sense to you: field; root of unity; Reed-Solomon code; sumcheck; Merkle tree; Schwartz-Zippel. Have you read Justin Thaler's book?

My real question is, how do you do it? What are your concrete strategies for tackling the math? More importantly, how do you read these papers and push through the difficult parts without getting discouraged? I will share notes from the ep once done.

@kobigurk I think this twitter thread is ok, it's pretty clear that this is an experiment.

@MatteoFrig60839 Good call, it’s now deleted to not confuse others. Might re-upload it letter with better framing What do you think about the rest of the experiment? Would you suggest I deleted the initial threads for the same reason?

@kobigurk So what's the plan? Are you going to leave the fake code and benchmarks on github for the benefit of future generations? Should I submit a story to hacker news "LLM beats Google geniuses" and see what happens? :-)

@MatteoFrig60839 The experiment being “not writing a line of code and seeing if CC will make it” :) I think for now it needs more hand holding from applied cryptographers

@johnAdebajo1 @jacobeverly @Google You can do whatever you want with the code, of course, but we don't plan to change the scope of the project.

@johnAdebajo1 @jacobeverly @Google Just to set expectations, this code is for the ZK presentation of government-issued identity documents in US Mobile Driver's licenses and the forthcoming EU Digital Identity wallets. It only contains stuff that the establishment would accept (i.e., SHA256 but not Poseidon).

ZK will be as big as key pair cryptography one day. @Google adopting the tech is one step in a very long journey. ZK is the endgame for the internet, not just web3 blog.google/technology/saf…