Secret-sharing for NP
From MaRDI portal
Publication:2397445
DOI10.1007/S00145-015-9226-0zbMATH Open1377.94057arXiv1403.5698OpenAlexW2282229740MaRDI QIDQ2397445FDOQ2397445
Authors: Ilan Komargodski, Moni Naor, Eylon Yogev 
Publication date: 22 May 2017
Published in: Journal of Cryptology (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1403.5698
Recommendations
- Secret-sharing for \(\mathbf {NP}\)
- Secret sharing for mNP: completeness results
- scientific article; zbMATH DE number 1676641
- On secret sharing schemes
- scientific article; zbMATH DE number 826065
- Progress in Cryptology - INDOCRYPT 2003
- scientific article; zbMATH DE number 2020870
- On the Power of Nonlinear Secret-Sharing
- A \((t,n)\) multi-secret sharing scheme
- Secret sharing schemes with nice access structures
Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Authentication, digital signatures and secret sharing (94A62)
Cites Work
- Probabilistic encryption
- How to share a secret
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- A Pseudorandom Generator from any One-way Function
- Bit commitment using pseudorandomness
- Multiple assignment scheme for sharing secret
- Secret-Sharing Schemes: A Survey
- Title not available (Why is that?)
- Title not available (Why is that?)
- Advances in Cryptology - CRYPTO 2003
- Candidate indistinguishability obfuscation and functional encryption for all circuits
- How to use indistinguishability obfuscation
- Title not available (Why is that?)
- Magic functions
- One-Way Functions and (Im)perfect Obfuscation
- Black-box obfuscation for \(d\)-CNFs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding
- On the Power of Nonlinear Secret-Sharing
- Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation
- Witness encryption and its applications
- Progress in Cryptology - INDOCRYPT 2003
- Cutting-edge cryptography through the lens of secret sharing
- Witness encryption from instance independent assumptions
- Indistinguishability obfuscation from semantically-secure multilinear encodings
- Protecting obfuscation against algebraic attacks
Cited In (12)
- Secret-sharing for \(\mathbf {NP}\)
- Secret sharing for mNP: completeness results
- Cutting-edge cryptography through the lens of secret sharing
- Cutting-edge cryptography through the lens of secret sharing
- Secure computation from one-way noisy communication, or: anti-correlation via anti-concentration
- Randomness recoverable secret sharing schemes
- Robust Distributed Pseudorandom Functions for mNP Access Structures
- NP-hardness of approximating meta-complexity: a cryptographic approach
- Succinct computational secret sharing
- One-Way Functions and (Im)perfect Obfuscation
- Distributed pseudorandom functions for general access structures in NP
- Witness encryption and its applications
This page was built for publication: Secret-sharing for NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397445)
