How to Share an NP Statement or Combiners for Zero-Knowledge Proofs
by Benny Applebaum and Eliran Kachlon
Oded's comments
I missed this work when posted on ECC; this was due to a combination
of personal reasons and a superficial impression that the focus of the
work is on issues that are far from my own interests.
Although I still don't have a concrete reason for me
to be interested in this work,
I find the result intriguing and thought-provoking.
Loosely speaking, for any $t \leq n$, the paper shows how
to deterministically transform
a Boolean circuit $C:\bitset^k\to\bitset$
to $n$ circuits $C_1,...,C_n:\bitset^m\to\bitset$
and randomly transform an assignment $x\in\bitset^k$ that satisfies $C$
into an assignment $y\in\bitset^n$ that satifies all $C_i$'s
such that the following conditions holds
- The circuit $C_i$ actually depends only on the bits at locations $S_i$,
where the $S_i\subset[m]$ have large pairwise intersection.
- The value of $y$ restricted to any $t-1$ of these sets
yields no information at all (i.e., essentially, the same distribution
can be generated based on $C$ (and the sequence of sets) alone).
- The value of $y$ restricted to any $t$ of these sets
yields a satisfying assignment to $C$.
A weaker notion is implicit in many zero-knowledge proofs.
For example, in the case of 3-colorability, the generated circuits
check variables that correspond to the endpoint of the edges,
the assignment to a single circuit yields no information at all,
whereas the assignment to all circuits yields a 3-coloring of the graph.
The zero-knowledge proof for Hamiltonitity yielkds two circuits
with a corresponding property; it is actually a 2-out-of-2 scheme
(in contrast to the 3-colorability scheme in which there is no sharp
zetro-vs-all threshold).
Original abstract
In Crypto'19, Goyal, Jain, and Sahai (GJS) introduced the elegant notion of *secret-sharing of an NP statement* (NPSS). Roughly speaking, a t-out-of-n secret sharing of an NP statement is a reduction that maps an instance-witness pair to n instance-witness pairs such that any subset of (t-1) reveals no information about the original witness, while any subset of t allows full recovery of the original witness. Although the notion was formulated for general t leq n, the only existing construction (due to GJS) applies solely to the case where t=n and provides only computational privacy. In this paper, we further explore NPSS and present the following contributions.
- **Definition.** We introduce a refined definition of information-theoretically secure NPSS. This notion can be seen as a cryptographic variant of standard NP-reductions and can be compiled into the GJS definition using any one-way function.
- **Construction.** We construct information-theoretic t-out-of-n NPSS for any values of t leq n with complexity polynomial in n. Along the way, we present a new notion of secure multiparty computation that may be of independent interest.
- **Applications.** Our NPSS framework enables the *non-interactive combination* of n instances of zero-knowledge proofs, where only ts of them are sound and only tz are zero-knowledge, provided that ts+tz greater than n. Our combiner preserves various desirable properties, such as the succinctness of the proof. Building on this, we establish the following results under the minimal assumption of one-way functions:
- *Standard NIZK implies NIZK in the Multi-String Model* (Groth and Ostrovsky, J. Cryptology, 2014), where security holds as long as a majority of the n common reference strings were honestly generated. Previously, such a transformation was only known in the common random string model, where the reference string is uniformly distributed.
- A *Designated-Prover NIZK in the Multi-String Model*, achieving a strong form of two-round Multi-Verifier Zero-Knowledge in the honest-majority setting.
- A *three-round secure multiparty computation protocol* for general functions in the honest-majority setting. The round complexity of this protocol is optimal, resolving a line of research that previously relied on stronger assumptions (Aharonov et al., Eurocrypt'12; Gordon et al., Crypto'15; Ananth et al., Crypto'18; Badrinarayanan et al., Asiacrypt'20; Applebaum et al., TCC'22).
See ECCC TR25-023.
Back to
list of Oded's choices.