CryptoDB
How to Share an NP Statement or Combiners for Zero-Knowledge Proofs
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | In Crypto'19, Goyal, Jain, and Sahai (GJS) introduced an 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 into $n$ instance/witness pairs such that any set of $(t-1)$ of them reveals no information on the original witness and any $t$ out of them allow to fully recover the original witness. While the notion was presented for general $t \leq n$, the only existing construction (due to GJS) applies only to the case where $t = n$ and achieves computational privacy. In this paper, we continue the study of NPSS and present the following contributions. **Definition:** We present a new refined definition of information-theoretic secure NPSS. This new notion can be viewed as a cryptographic variant of standard NP-reductions, and can be compiled into the GJS definition based on 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 allows us to *non-interactively* combine $n$ instances of zero-knowledge proofs that only $t_s$ of them are sound and only $t_z$ of them are zero-knowledge whenever $t_s+t_z>n$ while preserving various properties like the succinctness of the proof. Based on this, we prove the following results under the (minimal) assumption of the existence of one-way functions. (1) *Standard NIZK implies NIZK in the Multi-String model* (Groth and Ostrovsky; J. Cryptology, 2014), where in the latter model there are $n$ common reference strings and security holds as long as a majority of them were honestly generated. Previously, such a transformation was only known in the common *random* string model where the reference string is uniformly distributed. (2) A construction of *Designated-Prover NIZK in the Multi-String model* providing a strong notion of two-round Multi-Verifier Zero-Knowledge with honest-majority. (3) *Three-round secure multiparty computation protocol for general functions in the honest-majority setting*. The round complexity of this protocol is optimal, concluding a line of research that previously constructed such protocols based on stronger assumptions (Aharov et al., Eurocrypt'12; Gordon et al., Crypto'15; Ananth et al. Crypto'18; Badrinarayanan et al., Asiacrypt'20; Applebaum et al., TCC'22). |
BibTeX
@inproceedings{crypto-2025-35617,
title={How to Share an NP Statement or Combiners for Zero-Knowledge Proofs},
publisher={Springer-Verlag},
author={Benny Applebaum and Eliran Kachlon},
year=2025
}