Secret-Sharing for NP View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2016-01-14

AUTHORS

Ilan Komargodski, Moni Naor, Eylon Yogev

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
  • 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: 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

    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'

    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
     




    Preview window. Press ESC to close (or click here)


    ...