# Secret-Sharing for NP

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2016-01-14

AUTHORS 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 monotone Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing scheme. 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {P}}$$\end{document}). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}: 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. (Symposium on theory of computing conference, STOC, pp 467–476, 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement x∈L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\in L$$\end{document} for a language L∈NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L\in {\mathsf {NP}}$$\end{document} such that anyone holding a witness to the statement can decrypt the message; however, if x∉L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\notin L$$\end{document}, 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document} assuming witness encryption for NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document} and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}-complete function implies a computational secret-sharing scheme for every monotone function in NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}. More... »

PAGES

444-469

### References to SciGraph publications

• 1991-01. Bit commitment using pseudorandomness in JOURNAL OF CRYPTOLOGY
• 2015-12-24. Cutting-Edge Cryptography Through the Lens of Secret Sharing in THEORY OF CRYPTOGRAPHY
• 2001-08-02. On the (Im)possibility of Obfuscating Programs in ADVANCES IN CRYPTOLOGY — CRYPTO 2001
• 1993-03. Multiple assignment scheme for sharing secret in JOURNAL OF CRYPTOLOGY
• ### Journal

TITLE

Journal of Cryptology

ISSUE

2

VOLUME

30

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00145-015-9226-0

DOI

http://dx.doi.org/10.1007/s00145-015-9226-0

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1009468991

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Weizmann Institute of Science, Rehovot, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Weizmann Institute of Science, Rehovot, Israel"
],
"type": "Organization"
},
"familyName": "Komargodski",
"givenName": "Ilan",
"id": "sg:person.012204235441.12",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012204235441.12"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Weizmann Institute of Science, Rehovot, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Weizmann Institute of Science, Rehovot, Israel"
],
"type": "Organization"
},
"familyName": "Naor",
"givenName": "Moni",
"id": "sg:person.07776170271.83",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Weizmann Institute of Science, Rehovot, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Weizmann Institute of Science, Rehovot, Israel"
],
"type": "Organization"
},
"familyName": "Yogev",
"givenName": "Eylon",
"id": "sg:person.015120037757.44",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-662-49099-0_17",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041458690",
"https://doi.org/10.1007/978-3-662-49099-0_17"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02620229",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026401336",
"https://doi.org/10.1007/bf02620229"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf00196774",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003773885",
"https://doi.org/10.1007/bf00196774"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-44647-8_1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039594573",
"https://doi.org/10.1007/3-540-44647-8_1"
],
"type": "CreativeWork"
}
],
"datePublished": "2016-01-14",
"datePublishedReg": "2016-01-14",
"description": "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 \u201cqualified\u201d subset of parties can efficiently reconstruct the secret while any \u201cunqualified\u201d subset of parties cannot efficiently learn anything about the secret. The collection of \u201cqualified\u201d subsets is defined by a monotone Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing scheme. 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\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\mathsf {P}}$$\\end{document}). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in NP\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\mathsf {NP}}$$\\end{document}: in order to reconstruct the secret a set of parties must be \u201cqualified\u201d and provide a witness attesting to this fact. Recently, Garg\u00a0et al. (Symposium on theory of computing conference, STOC, pp 467\u2013476, 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement x\u2208L\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$x\\in L$$\\end{document} for a language L\u2208NP\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$L\\in {\\mathsf {NP}}$$\\end{document} such that anyone holding a witness to the statement can decrypt the message; however, if x\u2209L\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$x\\notin L$$\\end{document}, then it is computationally hard to decrypt. Garg\u00a0et 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\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\mathsf {NP}}$$\\end{document} assuming witness encryption for NP\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\mathsf {NP}}$$\\end{document} and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone NP\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\mathsf {NP}}$$\\end{document}-complete function implies a computational secret-sharing scheme for every monotone function in NP\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\mathsf {NP}}$$\\end{document}.",
"genre": "article",
"id": "sg:pub.10.1007/s00145-015-9226-0",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1136278",
"issn": [
"0933-2790",
"1432-1378"
],
"name": "Journal of Cryptology",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "2",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"secret-sharing scheme",
"subset of parties",
"set of parties",
"witness encryption",
"polynomial-size monotone circuits",
"one-way functions",
"cryptographic primitives",
"major open problem",
"encryption",
"monotone Boolean functions",
"open problem",
"candidate construction",
"secrets",
"scheme",
"messages",
"complete function",
"Boolean functions",
"same language",
"language",
"encrypt",
"decrypt",
"monotone circuits",
"primitives",
"set",
"Garg",
"parties",
"NPs",
"completeness theorem",
"monotone functions",
"subset",
"method",
"Yao",
"collection",
"construction",
"Rudich",
"concept",
"goal",
"et al",
"dealers",
"order",
"statements",
"function",
"monotone",
"main results",
"results",
"fact",
"possibility",
"circuit",
"witness",
"theorem",
"converse",
"al",
"consequences",
"problem"
],
"name": "Secret-Sharing for NP",
"pagination": "444-469",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1009468991"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00145-015-9226-0"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00145-015-9226-0",
"https://app.dimensions.ai/details/publication/pub.1009468991"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-10T10:14",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_696.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00145-015-9226-0"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00145-015-9226-0'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00145-015-9226-0'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00145-015-9226-0'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00145-015-9226-0'

This table displays all metadata directly associated to this object as RDF triples.

142 TRIPLES      22 PREDICATES      83 URIs      71 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author Ndea155f281e44ac7b5b12b7154947bca
4 schema:citation sg:pub.10.1007/3-540-44647-8_1
5 sg:pub.10.1007/978-3-662-49099-0_17
6 sg:pub.10.1007/bf00196774
7 sg:pub.10.1007/bf02620229
8 schema:datePublished 2016-01-14
9 schema:datePublishedReg 2016-01-14
10 schema:description 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 monotone Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing scheme. 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {P}}$$\end{document}). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}: 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. (Symposium on theory of computing conference, STOC, pp 467–476, 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement x∈L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\in L$$\end{document} for a language L∈NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L\in {\mathsf {NP}}$$\end{document} such that anyone holding a witness to the statement can decrypt the message; however, if x∉L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\notin L$$\end{document}, 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document} assuming witness encryption for NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document} and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}-complete function implies a computational secret-sharing scheme for every monotone function in NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}.
11 schema:genre article
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf Nd2ea62a3612e4d1babeb2ef14a857e51
15 Nf03f10a0a4e14493b8b589dd77c68c0c
16 sg:journal.1136278
17 schema:keywords Boolean functions
18 Garg
19 NPs
20 Rudich
21 Yao
22 al
23 candidate construction
24 circuit
25 collection
26 complete function
27 completeness theorem
28 concept
29 consequences
30 construction
31 converse
32 cryptographic primitives
33 dealers
34 decrypt
35 encrypt
36 encryption
37 et al
38 fact
39 function
40 goal
41 language
42 main results
43 major open problem
44 messages
45 method
46 monotone
47 monotone Boolean functions
48 monotone circuits
49 monotone functions
50 one-way functions
51 open problem
52 order
53 parties
54 polynomial-size monotone circuits
55 possibility
56 primitives
57 problem
58 results
59 same language
60 scheme
61 secret-sharing scheme
62 secrets
63 set
64 set of parties
65 statements
66 subset
67 subset of parties
68 theorem
69 witness
70 witness encryption
71 schema:name Secret-Sharing for NP
72 schema:pagination 444-469
73 schema:productId Nd6d1f14e503d4d9797aac6ea7ccfa78d
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009468991
76 https://doi.org/10.1007/s00145-015-9226-0
77 schema:sdDatePublished 2022-05-10T10:14
80 schema:url https://doi.org/10.1007/s00145-015-9226-0
82 sgo:sdDataset articles
83 rdf:type schema:ScholarlyArticle
84 N7afb1a8ad3cd43e49dd8be2807ab6782 schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 N97dc7bda389c48feb921144f5b833ef0 rdf:first sg:person.07776170271.83
87 rdf:rest Ndfb30d7d180a478aa9d2f046865f9374
88 Nd2ea62a3612e4d1babeb2ef14a857e51 schema:issueNumber 2
89 rdf:type schema:PublicationIssue
90 Nd6d1f14e503d4d9797aac6ea7ccfa78d schema:name doi
91 schema:value 10.1007/s00145-015-9226-0
92 rdf:type schema:PropertyValue
93 Ndea155f281e44ac7b5b12b7154947bca rdf:first sg:person.012204235441.12
94 rdf:rest N97dc7bda389c48feb921144f5b833ef0
95 Ndfb30d7d180a478aa9d2f046865f9374 rdf:first sg:person.015120037757.44
96 rdf:rest rdf:nil
98 rdf:type schema:PublicationVolume
100 schema:value pub.1009468991
101 rdf:type schema:PropertyValue
102 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
103 schema:name Information and Computing Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
106 schema:name Computation Theory and Mathematics
107 rdf:type schema:DefinedTerm
108 sg:journal.1136278 schema:issn 0933-2790
109 1432-1378
110 schema:name Journal of Cryptology
111 schema:publisher Springer Nature
112 rdf:type schema:Periodical
113 sg:person.012204235441.12 schema:affiliation grid-institutes:grid.13992.30
114 schema:familyName Komargodski
115 schema:givenName Ilan
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012204235441.12
117 rdf:type schema:Person
118 sg:person.015120037757.44 schema:affiliation grid-institutes:grid.13992.30
119 schema:familyName Yogev
120 schema:givenName Eylon
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44
122 rdf:type schema:Person
123 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
124 schema:familyName Naor
125 schema:givenName Moni
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
127 rdf:type schema:Person
128 sg:pub.10.1007/3-540-44647-8_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039594573
129 https://doi.org/10.1007/3-540-44647-8_1
130 rdf:type schema:CreativeWork
131 sg:pub.10.1007/978-3-662-49099-0_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041458690
132 https://doi.org/10.1007/978-3-662-49099-0_17
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/bf00196774 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003773885
135 https://doi.org/10.1007/bf00196774
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/bf02620229 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026401336
138 https://doi.org/10.1007/bf02620229
139 rdf:type schema:CreativeWork
140 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Rehovot, Israel
141 schema:name Weizmann Institute of Science, Rehovot, Israel
142 rdf:type schema:Organization