Secret-sharing for NP
From MaRDI portal
Publication:2397445
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.
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
Cites work
- scientific article; zbMATH DE number 4179276 (Why is no real title available?)
- scientific article; zbMATH DE number 4008289 (Why is no real title available?)
- scientific article; zbMATH DE number 176869 (Why is no real title available?)
- scientific article; zbMATH DE number 1024051 (Why is no real title available?)
- scientific article; zbMATH DE number 1842483 (Why is no real title available?)
- A Pseudorandom Generator from any One-way Function
- Advances in Cryptology - CRYPTO 2003
- Bit commitment using pseudorandomness
- Black-box obfuscation for \(d\)-CNFs
- Candidate indistinguishability obfuscation and functional encryption for all circuits
- Cutting-edge cryptography through the lens of secret sharing
- How to share a secret
- How to use indistinguishability obfuscation
- Indistinguishability obfuscation from semantically-secure multilinear encodings
- Magic functions
- Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation
- Multiple assignment scheme for sharing secret
- On the Power of Nonlinear Secret-Sharing
- One-Way Functions and (Im)perfect Obfuscation
- Probabilistic encryption
- Progress in Cryptology - INDOCRYPT 2003
- Protecting obfuscation against algebraic attacks
- Secret-Sharing Schemes: A Survey
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding
- Witness encryption and its applications
- Witness encryption from instance independent assumptions
Cited in
(12)- Distributed pseudorandom functions for general access structures in NP
- 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
- NP-hardness of approximating meta-complexity: a cryptographic approach
- Succinct computational secret sharing
- Robust Distributed Pseudorandom Functions for mNP Access Structures
- Randomness recoverable secret sharing schemes
- One-Way Functions and (Im)perfect Obfuscation
- Secure computation from one-way noisy communication, or: anti-correlation via anti-concentration
- 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)
