Paper 2014/213

Secret-Sharing for NP

Ilan Komargodski, Moni Naor, and Eylon Yogev

Abstract

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 Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing schemes. 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 P). Around 1990 Rudich raised the possibility of obtaining secret-sharing 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 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 NP assuming witness encryption for NP and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone NP-complete function implies a computational secret-sharing scheme for every monotone function in NP.

Metadata
Available format(s)
PDF
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
2015-05-31: last of 7 revisions
2014-03-24: received
See all versions
Short URL
https://ia.cr/2014/213
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/213,
      author = {Ilan Komargodski and Moni Naor and Eylon Yogev},
      title = {Secret-Sharing for {NP}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/213},
      year = {2014},
      url = {https://eprint.iacr.org/2014/213}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.