Paper 2014/213
SecretSharing for NP
Ilan Komargodski, Moni Naor, and Eylon Yogev
Abstract
A computational secretsharing 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 Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secretsharing schemes. Yao suggested a method for secretsharing for any function that has a polynomialsize monotone circuit (a class which is strictly smaller than the class of monotone functions in P). Around 1990 Rudich raised the possibility of obtaining secretsharing for all monotone functions in 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. (STOC 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 NP such that anyone holding a witness to the statement can decrypt the message, however, if x is not in 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 secretsharing implies witness encryption for the same language. Our main result is the converse: we give a construction of a computational secretsharing scheme for any monotone function in NP assuming witness encryption for NP and oneway functions. As a consequence we get a completeness theorem for secretsharing: computational secretsharing scheme for any single monotone NPcomplete function implies a computational secretsharing scheme for every monotone function in NP.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2014
 Keywords
 secret sharingobfuscation
 Contact author(s)
 eylon yogev @ weizmann ac il
 History
 20150531: last of 7 revisions
 20140324: received
 See all versions
 Short URL
 https://ia.cr/2014/213
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/213, author = {Ilan Komargodski and Moni Naor and Eylon Yogev}, title = {SecretSharing for {NP}}, howpublished = {Cryptology ePrint Archive, Paper 2014/213}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/213}}, url = {https://eprint.iacr.org/2014/213} }