Paper 2025/240

Robust Non-Interactive Zero-Knowledge Combiners

Lorenzo Magliocco, Sapienza University of Rome

Daniele Venturi, Sapienza University of Rome

Yu Xia, The University of Edinburgh

Abstract

A $t$-out-of-$n$ robust non-interactive zero-knowledge (NIZK) combiner is a construction that, given access to $n$ candidate instantiations of a NIZK for some language, itself implements a NIZK for the same language. Moreover, the combiner is secure, assuming at least $t$ of the given candidates are secure. In this work, we provide the first definition of combiners for NIZK, and prove that no robust NIZK combiner exists assuming $t \le \lfloor n/2 \rfloor$ (unless the polynomial hierarchy collapses). On the positive side, we provide different constructions of robust NIZK combiners for $t > \lfloor n/2 \rfloor$. In particular, we show how to obtain: 1) A black-box combiner working for a special class of {\em homomorphic} languages where $n,t$ are polynomial and $t > \lfloor n/2 \rfloor$. 2) A non-black-box combiner working for any language, where $n,t$ are constant and $t > \lfloor n/2 \rfloor$. 3) A non-black-box combiner working for any language, where $n,t$ are polynomial and $t > \lfloor 2n/3 \rfloor$.

Note: Eurocrypt 2026 full version. Improved presentation; expanded impossibility results.

@misc{cryptoeprint:2025/240,
      author = {Michele Ciampi and Lorenzo Magliocco and Daniele Venturi and Yu Xia},
      title = {Robust Non-Interactive Zero-Knowledge Combiners},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/240},
      year = {2025},
      url = {https://eprint.iacr.org/2025/240}
}