Paper 2026/1148

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

Dmitry Krachun, Princeton University

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^2+\lambda)$ additions, which can be smaller when $n\log n <\lambda$. We highlight the impact of reducing the number of additions on aggregation of group-based commitments, such as KZG commitments[KZG10]. We pose improving this further to $O(n+\lambda)$ as an interesting open problem.

Note: figure explaining differencing