How to Share an NP Statement or Combiners for Zero-Knowledge Proofs
摘要
In Crypto’19, Goyal, Jain, and Sahai (GJS) introduced the elegant notion of secret-sharing of an \(\textbf{NP}\) statement (NPSS). Roughly speaking, a \(t\) -out-of- \(n\) secret sharing of an \(\textbf{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 \le 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.