Giacomo Fenzi
@giacomofenzi.bsky.social
PhD student @EPFL, previously @ETH
Interested in cryptography at large, post quantum and interactive proofs in particular.
Interista alla Prisco.
Interested in cryptography at large, post quantum and interactive proofs in particular.
Interista alla Prisco.
Go read the paper!
📚: eprint.iacr.org/2025/2065.pdf
Special thanks to @succinctlabs.bsky.social and @simonsinstitute.bsky.social where this work was mainly done!
📚: eprint.iacr.org/2025/2065.pdf
Special thanks to @succinctlabs.bsky.social and @simonsinstitute.bsky.social where this work was mainly done!
eprint.iacr.org
November 13, 2025 at 10:11 AM
Go read the paper!
📚: eprint.iacr.org/2025/2065.pdf
Special thanks to @succinctlabs.bsky.social and @simonsinstitute.bsky.social where this work was mainly done!
📚: eprint.iacr.org/2025/2065.pdf
Special thanks to @succinctlabs.bsky.social and @simonsinstitute.bsky.social where this work was mainly done!
Towards the result, we formalize a few notions previously implicit in the literature, that might be of independent interest such as: (i) interactive oracle commitment schemes; and (ii) the right-extension of a linear code which captures how “code switchable” a code is.
November 13, 2025 at 10:11 AM
Towards the result, we formalize a few notions previously implicit in the literature, that might be of independent interest such as: (i) interactive oracle commitment schemes; and (ii) the right-extension of a linear code which captures how “code switchable” a code is.
Tensorswitch is very flexible, being both field-agnostic and code-agnostic.
It yields PCD matching WARP’s theoretical efficiency while also achieving a sublinear accumulator, making it suitable for distributed proving.
Plus, it should be great for committing to sparse data.
It yields PCD matching WARP’s theoretical efficiency while also achieving a sublinear accumulator, making it suitable for distributed proving.
Plus, it should be great for committing to sparse data.
November 13, 2025 at 10:11 AM
Tensorswitch is very flexible, being both field-agnostic and code-agnostic.
It yields PCD matching WARP’s theoretical efficiency while also achieving a sublinear accumulator, making it suitable for distributed proving.
Plus, it should be great for committing to sparse data.
It yields PCD matching WARP’s theoretical efficiency while also achieving a sublinear accumulator, making it suitable for distributed proving.
Plus, it should be great for committing to sparse data.
Further, our scheme is promising for concrete efficiency:
- Commit time is roughly one encoding and 3n multiplications
- Prover time is roughly 6n multiplications (and requires no committing to large extension field messages)
- Query complexity is optimal for a tensor code
- Commit time is roughly one encoding and 3n multiplications
- Prover time is roughly 6n multiplications (and requires no committing to large extension field messages)
- Query complexity is optimal for a tensor code
November 13, 2025 at 10:11 AM
Further, our scheme is promising for concrete efficiency:
- Commit time is roughly one encoding and 3n multiplications
- Prover time is roughly 6n multiplications (and requires no committing to large extension field messages)
- Query complexity is optimal for a tensor code
- Commit time is roughly one encoding and 3n multiplications
- Prover time is roughly 6n multiplications (and requires no committing to large extension field messages)
- Query complexity is optimal for a tensor code
We construct a hash-based polynomial commitment scheme that is asymptotically optimal in most parameters: linear prover time, O(lambda) query complexity and logarithmic verifier time.
November 13, 2025 at 10:11 AM
We construct a hash-based polynomial commitment scheme that is asymptotically optimal in most parameters: linear prover time, O(lambda) query complexity and logarithmic verifier time.
Finally, we show how modifications of the sumcheck protocol can achieve better time-space tradeoffs, and present (log^*N + k)-round protocols that run in time O(N * (log^* + k)) and space O(N^1/k) (and achieve linear time in the O(N) space setting).
August 14, 2025 at 2:36 PM
Finally, we show how modifications of the sumcheck protocol can achieve better time-space tradeoffs, and present (log^*N + k)-round protocols that run in time O(N * (log^* + k)) and space O(N^1/k) (and achieve linear time in the O(N) space setting).
Perhaps surprisingly, we show that the log log N factor is inherent, unless the exponent in matrix multiplication is 2 (in that case, we can recover the single multilinear tradeoff).
Further, we show that the tradeoff in Blendy was optimal.
Further, we show that the tradeoff in Blendy was optimal.
August 14, 2025 at 2:36 PM
Perhaps surprisingly, we show that the log log N factor is inherent, unless the exponent in matrix multiplication is 2 (in that case, we can recover the single multilinear tradeoff).
Further, we show that the tradeoff in Blendy was optimal.
Further, we show that the tradeoff in Blendy was optimal.
We fix this, and show a sumcheck algorithm that runs in time O(N * (log log N + k)) and uses space O(N^1/k). This algorithm is concretely efficient, using up to 120x less memory at ~2x prover slowdown compared to non-space efficient alternatives.
August 14, 2025 at 2:36 PM
We fix this, and show a sumcheck algorithm that runs in time O(N * (log log N + k)) and uses space O(N^1/k). This algorithm is concretely efficient, using up to 120x less memory at ~2x prover slowdown compared to non-space efficient alternatives.
In previous work, we showed that, for sumcheck claims about a single multilinear and any parameter k, there is a sumcheck algorithm that runs in time O(k * N) and space O(N^1/k). Annoyingly, we couldn’t find an equivalent for products.
August 14, 2025 at 2:36 PM
In previous work, we showed that, for sumcheck claims about a single multilinear and any parameter k, there is a sumcheck algorithm that runs in time O(k * N) and space O(N^1/k). Annoyingly, we couldn’t find an equivalent for products.
Easy optimizations such as path pruning should improve proof size significantly. Sometimes the proofs also just contain some random trash (see below), which we could, um, avoid sending. Read the paper for more!
August 12, 2025 at 10:52 PM
Easy optimizations such as path pruning should improve proof size significantly. Sometimes the proofs also just contain some random trash (see below), which we could, um, avoid sending. Read the paper for more!
For the serious part of this post, this in fact should not happen, hash based proofs should be not-compressible. The fact that they are hints at serialization being suboptimal, and we should improve (as a community) to achieve proof size reduction at minimal cost.
August 12, 2025 at 10:52 PM
For the serious part of this post, this in fact should not happen, hash based proofs should be not-compressible. The fact that they are hints at serialization being suboptimal, and we should improve (as a community) to achieve proof size reduction at minimal cost.
Surprisingly, this leads to a reduction *across the board on proof size*, on each proof system that we tested (including ones I had written, and except for Ligerito, damn you Julia!), which is why we recommend to zip your proofs always.
August 12, 2025 at 10:52 PM
Surprisingly, this leads to a reduction *across the board on proof size*, on each proof system that we tested (including ones I had written, and except for Ligerito, damn you Julia!), which is why we recommend to zip your proofs always.
We, um, just ran zip on them.
August 12, 2025 at 10:52 PM
We, um, just ran zip on them.
This has caused some headaches, which we found a great solution to using some relatively unknown techniques from information theory, buried in some papers published in 70s, leading to proof size reduction to as much as 60% of the original size!
August 12, 2025 at 10:52 PM
This has caused some headaches, which we found a great solution to using some relatively unknown techniques from information theory, buried in some papers published in 70s, leading to proof size reduction to as much as 60% of the original size!
Hash-based proofs tend to be larger than their elliptic curve counterparts, and a focus of the ethproofs.org initiative is to compress them to minimize the bandwidth requirements of validators
August 12, 2025 at 10:52 PM
Hash-based proofs tend to be larger than their elliptic curve counterparts, and a focus of the ethproofs.org initiative is to compress them to minimize the bandwidth requirements of validators
I want to thank my wonderful collaborators that have already been involved in this effort:
Gal Arnon, Remco Bloemen, Benedikt Bünz, Thomas Coratger, Ale Chiesa, @xyz-pierre.bsky.social, Eylon Yogev and William Wang.
Hope we can continue doing great work going forward ;)
Gal Arnon, Remco Bloemen, Benedikt Bünz, Thomas Coratger, Ale Chiesa, @xyz-pierre.bsky.social, Eylon Yogev and William Wang.
Hope we can continue doing great work going forward ;)
July 22, 2025 at 4:03 PM
I want to thank my wonderful collaborators that have already been involved in this effort:
Gal Arnon, Remco Bloemen, Benedikt Bünz, Thomas Coratger, Ale Chiesa, @xyz-pierre.bsky.social, Eylon Yogev and William Wang.
Hope we can continue doing great work going forward ;)
Gal Arnon, Remco Bloemen, Benedikt Bünz, Thomas Coratger, Ale Chiesa, @xyz-pierre.bsky.social, Eylon Yogev and William Wang.
Hope we can continue doing great work going forward ;)
This grant allows me to investigate how the recent advances in hash-based arguments and accumulation schemes (such as Blaze, FICS, FACS, STIR, WHIR and WARP) fit in Ethereum post-quantum transition, leading to an efficient and secure quantum-safe consensus.
(5/n)
(5/n)
July 22, 2025 at 4:03 PM
This grant allows me to investigate how the recent advances in hash-based arguments and accumulation schemes (such as Blaze, FICS, FACS, STIR, WHIR and WARP) fit in Ethereum post-quantum transition, leading to an efficient and secure quantum-safe consensus.
(5/n)
(5/n)
SNARKs reduce verifying many signatures to verifying a single proof.
Hash-based succinct arguments offer conservative security against quantum adversaries, and have consolidated themselves as concretely efficient in all parameters of interest.
(4/n)
Hash-based succinct arguments offer conservative security against quantum adversaries, and have consolidated themselves as concretely efficient in all parameters of interest.
(4/n)
July 22, 2025 at 4:03 PM
SNARKs reduce verifying many signatures to verifying a single proof.
Hash-based succinct arguments offer conservative security against quantum adversaries, and have consolidated themselves as concretely efficient in all parameters of interest.
(4/n)
Hash-based succinct arguments offer conservative security against quantum adversaries, and have consolidated themselves as concretely efficient in all parameters of interest.
(4/n)
Among hash-based schemes, XMSS signatures have emerged (ia.cr/2025/055) as an attractive candidate due to small proof sizes and concrete efficiency.
However, they lack homomorphic properties, which makes aggregation challenging.
We can solve this using SNARKs.
(3/n)
However, they lack homomorphic properties, which makes aggregation challenging.
We can solve this using SNARKs.
(3/n)
Hash-Based Multi-Signatures for Post-Quantum Ethereum
With the threat posed by quantum computers on the horizon, systems like Ethereum must transition to cryptographic primitives resistant to quantum attacks. One of the most critical of these primitives ...
ia.cr
July 22, 2025 at 4:03 PM
Among hash-based schemes, XMSS signatures have emerged (ia.cr/2025/055) as an attractive candidate due to small proof sizes and concrete efficiency.
However, they lack homomorphic properties, which makes aggregation challenging.
We can solve this using SNARKs.
(3/n)
However, they lack homomorphic properties, which makes aggregation challenging.
We can solve this using SNARKs.
(3/n)