2016-01-14
AUTHORSIlan Komargodski, Moni Naor, Eylon Yogev
ABSTRACTA 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... »
PAGES444-469
http://scigraph.springernature.com/pub.10.1007/s00145-015-9226-0
DOIhttp://dx.doi.org/10.1007/s00145-015-9226-0
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1009468991
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"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",
"volumeNumber": "30"
}
],
"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",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"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"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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'
Turtle is a human-readable linked data format.
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 | |
|---|---|---|---|
| 1 | sg:pub.10.1007/s00145-015-9226-0 | schema:about | anzsrc-for:08 |
| 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 |
| 74 | ″ | ″ | Nf57c2982025641628a56b33ad069d60b |
| 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 |
| 78 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
| 79 | ″ | schema:sdPublisher | N7afb1a8ad3cd43e49dd8be2807ab6782 |
| 80 | ″ | schema:url | https://doi.org/10.1007/s00145-015-9226-0 |
| 81 | ″ | sgo:license | sg:explorer/license/ |
| 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 |
| 97 | Nf03f10a0a4e14493b8b589dd77c68c0c | schema:volumeNumber | 30 |
| 98 | ″ | rdf:type | schema:PublicationVolume |
| 99 | Nf57c2982025641628a56b33ad069d60b | schema:name | dimensions_id |
| 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 |