Lightnews — Scholar-powered news

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 14

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).

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 14

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.

1

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 14

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.

1

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 14

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.

1

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 14

Back to actual research…
We present a family of space-efficient sumcheck algorithms, and show that they are optimal! 🍹

Joint work with Anubhav, Ale, Elisabetta, @zkproofs.bsky.social, Tushar and Andrew

📚: ia.cr/2025/1473
🧑🏻‍💻: github.com/compsec-epfl...

1 2 6

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 12

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!

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 12

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.

1

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 12

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.

1

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 12

We, um, just ran zip on them.

1

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 12

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!

1 2

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 12

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

1

Giacomo Fenzi @giacomofenzi.bsky.social · Aug 12

Excited to share the new frontier of reducing hash-based SNARKs proof size: a post-quantum secure lightweight black-box technique to reduce proof size to 60% of the original one!

w/ my wonderful coauthor Yuwen Zhang.

ia.cr/2025/1446

1 1 7

Reposted by Giacomo Fenzi

Miro Haller @mirohaller.bsky.social · Aug 11

Our WOOT paper went out of disclosure today. We found 5 attacks on the Master Lock D1000 which allow unauthorized unlocking, bypassing access revocation, forging log entries, and causing DoS.

If you're in Seattle, come to our talk given by Chengsong, one of the students I mentored for this paper.

Attack 1 (session replay): An adversary in physical proximity of the lock (without ever having a valid account on the lock) can record the Bluetooth Low Energy (BLE) communication of a whole session and replay it to repeat all executed commands, including unlocking the lock.
Attack 2 (exceeding access): Former guests can continue unlocking the lock after their access has been revoked.
Attack 3 (clock tampering): Malicious guests can adjust the clock time of the smart lock arbitrarily, extending their own access past expiration or locking out all legitimate users.
Attack 4 (audit log tampering): An adversary that only knows the lock’s identifier (which is advertised over BLE) can upload arbitrary audit events to the telemetry server, and prevent legitimate audit events from being uploaded. Hence, the adversary can hide their own activities.
Attack 5 (malformed messages): Without valid access, an adversary can send malformed BLE messages to the lock that make it unresponsive or corrupt memory, which results in a Denial of Service (DoS) for authorized users. A malicious authorized user can even leak the memory of the smart lock.

2 3 9

Giacomo Fenzi @giacomofenzi.bsky.social · Jul 23

Thank you!!!

1

Giacomo Fenzi @giacomofenzi.bsky.social · Jul 22

thank you!!!

Giacomo Fenzi @giacomofenzi.bsky.social · Jul 22

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 ;)

1

Giacomo Fenzi @giacomofenzi.bsky.social · Jul 22

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)

1 2

Giacomo Fenzi @giacomofenzi.bsky.social · Jul 22

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)

1

Giacomo Fenzi @giacomofenzi.bsky.social · Jul 22

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)

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

1

Giacomo Fenzi @giacomofenzi.bsky.social · Jul 22

Currently, BLS signatures are used for this role, and they shine due to their aggregation properties.
However, the same homomorphisms that makes them aggregatable also makes them insecure against quantum computers.
Hash-based signatures and arguments offer an alternative.
(2/n)

1

Giacomo Fenzi @giacomofenzi.bsky.social · Jul 22

Signatures are a powerful cryptographic primitive, used broadly in the Ethereum protocol.
Within consensus, they are used by validators to designate a new consensus state.
To reduce bandwidth requirement, the signatures are aggregated before propagation to the network.
(1/n)

1

Giacomo Fenzi @giacomofenzi.bsky.social · Jul 22

Excited to share that I've been awarded a research grant from the @ethereum.foundation under the 2025 Academic Grants Round to explore how Ethereum can be made secure against quantum adversaries using hash-based arguments: a critical step for the long-term resilience of the network
🧵👇

A visualization on how signatures and aggregation are used within the Ethereum network: validator agree on a state, they sign and the signatures are then aggregated and propagated to the network.

3 16

Giacomo Fenzi @giacomofenzi.bsky.social · May 28

I suggest giving the attacker a fully identity, makes the paper feel more real.
For me, it’s Giulio Rossi, a ferramenta from Abbiategrasso with a lovely family who hides a dark and tumultuous past in quantum random oracles

1 5

Reposted by Giacomo Fenzi

Christian Knabenhans @cknabs.bsky.social · May 20

I'm happy to finally open-source lattirust, a library for lattice-based zero-knowledge/succinct arguments! Lattirust is somewhat like arkworks, but for lattices; and like lattigo, but for arguments.

➔ github.com/lattirust

lattirust

Lattice zero-knowledge/succinct arguments, and more - lattirust

github.com

2 16 32

Giacomo Fenzi @giacomofenzi.bsky.social · May 15

It forces you to specify a domain separator at the start, which basically is a list of the squeeze/absorb operations in the protocol. If you deviate from that, the sponge will panick.
To achieve the third I actually have a proposal, but no time to implement...

2