Secret-sharing for NP

DOI10.1007/S00145-015-9226-0zbMATH Open1377.94057arXiv1403.5698OpenAlexW2282229740MaRDI QIDQ2397445FDOQ2397445

Eylon Yogev, Moni Naor, Ilan Komargodski

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

zbMATH Keywords

secret-sharingobfuscationwitness encryption

Mathematics Subject Classification ID

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 (8)

• Distributed Pseudorandom Functions for General Access Structures in NP
• 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

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)