Paper 2026/1148

Pushing the boundaries of group-based aggregation with zero-evading generators of low additive complexity

Abstract

A zero-evading generator with error parameter $\lambda$ is a distribution $Z$ on $\mathbb{F}^n$ such that for any non-zero vector $x\in \mathbb{F}^n$ the probability that $<a,x>=0$ is at most $2^{-\lambda}$, when $a$ is chosen according to $Z$. We investigate the number of additions required to compute $<a,x>$ given $x$. The traditional construction chooses a vector $a$ with random $\lambda$-bit elements. Pippenger's algorithm gives an additive complexity of at least $\Omega(\lambda n/\log n)$ for this approach. We give a construction requiring only $O(n+\lambda)$ additions. We highlight the impact of reducing the number of additions on aggregation of group-based commitments, such as KZG commitments[KZG10].

Note: Druk-Ishai codes for better asymptotics