Robust Non-interactive Zero-Knowledge Combiners

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