Secret-Sharing for NP

A computational secret-sharing scheme is a method that enables a dealer, that has a secret, to distribute this secret among a set of parties such that a “qualified” subset of parties can efficiently reconstruct the secret while any “unqualified” subset of parties cannot efficiently learn anything about the secret. The collection of “qualified” subsets is defined by a monotone Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing scheme. Yao suggested a method for secret-sharing for any function that has a polynomial-size monotone circuit (a class which is strictly smaller than the class of monotone functions in \({\mathsf {P}}\)). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in \({\mathsf {NP}}\): in order to reconstruct the secret a set of parties must be “qualified” and provide a witness attesting to this fact. Recently, Garg et al. (Symposium on theory of computing conference, STOC, pp 467–476, 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement \(x\in L\) for a language \(L\in {\mathsf {NP}}\) such that anyone holding a witness to the statement can decrypt the message; however, if \(x\notin L\), then it is computationally hard to decrypt. Garg et al. showed how to construct several cryptographic primitives from witness encryption and gave a candidate construction. One can show that computational secret-sharing implies witness encryption for the same language. Our main result is the converse: we give a construction of a computational secret-sharing scheme for any monotone function in \({\mathsf {NP}}\) assuming witness encryption for \({\mathsf {NP}}\) and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone \({\mathsf {NP}}\)-complete function implies a computational secret-sharing scheme for every monotone function in \({\mathsf {NP}}\).