Abstract

In Crypto'19, Goyal, Jain, and Sahai 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 a circuit-SAT instance f into n circuit-SAT instances (f_1, ..., f_n) over a common set of variables, such that: (1) Given a satisfying assignment x for f, it is possible to sample partial assignments (y_1,...,y_n) that consistently satisfy (f_1,...,f_n), and where the marginal distribution of every collection of t-1 partial assignments leaks no information about the witness x; (2) Conversely, any collection of t partial assignments that consistently satisfy t of the instances can be efficiently translated into an assignment x that satisfies f.

We present the first information-theoretic construction of NPSS for arbitrary values of t and n. Previously, it was only known how to achieve computational privacy for the special case of t=n. Our constructions rely on a new notion of secure multiparty computation protocols that may be of independent interest. We use our NPSS to obtain several applications in the domain of zero-knowledge proofs and secure-multiparty computation. If time permits, we will also discuss a related construction of leakage-resilient NPSS that gives rise to NIZK amplifiers resolving open questions of Goyal, Jain, and Sahai (Crypto'19) and Bitansky and Geier (Crypto'24).

Based on joint works with Eliran Kachlon.

Video Recording