How to Share an NP Statement or Combiners for Zero-Knowledge Proofs
summary
Claims an information-theoretic construction of t-out-of-n NPSS for arbitrary t and n, built from a new MPC primitive realizable in the OT hybrid model, and used as the combinatorial core to implement multistring NIZKs for arbitrary CRS and a three-round honest-majority MPC with guaranteed output delivery based only on one-way functions. Constructions include a leakage-resilient variant that yields NIZK amplifiers; protocols are concrete, polynomial-time, and demonstrated to meet the stated privacy and recovery thresholds.
AI-written summary · about
chapters (15)
- 0:00Combiners for ZK proofs
- 1:06Combining TAs for ZK proofs
- 3:59Secret sharing vs NP statements
- 7:10Naive NPSS definition impossible
- 9:39Relaxing NPSS with partial assignments
- 13:14NPSS main result and prior work
- 14:23ZK proof combining applications
- 16:50Multistring NIZK advantages
- 18:35Building multistring NIZK with NPSS
- 21:48Designated prover NIZK extension
- 23:35Two-round MVZK proofs
- 24:21New MPC notion for NPSS
- 28:27NPSS from MPC in the head
- 30:17Summary and open questions
- 31:19NIZK complication follow-up
related talks
01h 13mA Zero-Knowledge PCP Theorem
38mNew Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ...
28mZero Knowledge Proofs and Their Future Applications
29mKolmogorov Complexity Characterizes Statistical Zero Knowledge
23mZKBoo: Faster Zero-Knowledge for Boolean Circuits
56mCollaborative zk-SNARKs: Proving as One over Distributed Secrets
49mHard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
33mA New Approach for Non-Interactive Zero-Knowledge from Learning with Errors