You are here:   
  1. Home
  2. Articles
  3. http://scigraph.springernature.com/pub.10.1007/s00145-015-9226-0

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
  • 2001-08-02. On the (Im)possibility of Obfuscating Programs in ADVANCES IN CRYPTOLOGY — CRYPTO 2001
  • 2015-12-24. Cutting-Edge Cryptography Through the Lens of Secret Sharing in THEORY OF CRYPTOGRAPHY
  • 1993-03. Multiple assignment scheme for sharing secret in JOURNAL OF CRYPTOLOGY

    • Journal

    TITLE

    Journal of Cryptology

    ISSUE

    2

    VOLUME

    30

    Subjects

  • FOR: Information And Computing Sciences
  • FOR: Computation Theory And Mathematics

    • Author Affiliations

  • Weizmann Institute of Science, Rehovot, Israel

    • 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/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"
      }, 
      {
        "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/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"
      }
    ], 
    "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", 
      "set of parties", 
      "subset of parties", 
      "witness encryption", 
      "polynomial-size monotone circuits", 
      "one-way functions", 
      "major open problem", 
      "cryptographic primitives", 
      "encryption", 
      "open problem", 
      "candidate construction", 
      "monotone Boolean functions", 
      "scheme", 
      "secrets", 
      "messages", 
      "Boolean functions", 
      "encrypt", 
      "language", 
      "same language", 
      "monotone circuits", 
      "decrypt", 
      "primitives", 
      "set", 
      "Garg", 
      "monotone functions", 
      "completeness theorem", 
      "NP", 
      "parties", 
      "method", 
      "subset", 
      "Yao", 
      "construction", 
      "Rudich", 
      "et al", 
      "collection", 
      "concept", 
      "goal", 
      "order", 
      "function", 
      "statements", 
      "dealers", 
      "circuit", 
      "main results", 
      "monotone", 
      "fact", 
      "results", 
      "theorem", 
      "possibility", 
      "witness", 
      "al", 
      "converse", 
      "consequences", 
      "problem", 
      "computational secret-sharing scheme", 
      "single monotone"
    ], 
    "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-01-01T18:40", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_697.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.

    143 TRIPLES      22 PREDICATES      84 URIs      72 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 Nfc10ce25a1fa462c8d40e5ae33acadd7
    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 N27502fd2ee3e4e368c58fb2343f91b35
    15 ″ ″ N2a6f1c083bf440c991684fc940e294c6
    16 ″ ″ sg:journal.1136278
    17 ″ schema:keywords Boolean functions
    18 ″ ″ Garg
    19 ″ ″ NP
    20 ″ ″ Rudich
    21 ″ ″ Yao
    22 ″ ″ al
    23 ″ ″ candidate construction
    24 ″ ″ circuit
    25 ″ ″ collection
    26 ″ ″ completeness theorem
    27 ″ ″ computational secret-sharing scheme
    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 ″ ″ single monotone
    66 ″ ″ statements
    67 ″ ″ subset
    68 ″ ″ subset of parties
    69 ″ ″ theorem
    70 ″ ″ witness
    71 ″ ″ witness encryption
    72 ″ schema:name Secret-Sharing for NP
    73 ″ schema:pagination 444-469
    74 ″ schema:productId N664d7f60a2f74d3e9b59acb1c157b721
    75 ″ ″ Nc75c97e902fb480099a282a1264b0bb4
    76 ″ schema:sameAs https://app.dimensions.ai/details/publication/pub.1009468991
    77 ″ ″ https://doi.org/10.1007/s00145-015-9226-0
    78 ″ schema:sdDatePublished 2022-01-01T18:40
    79 ″ schema:sdLicense https://scigraph.springernature.com/explorer/license/
    80 ″ schema:sdPublisher Nb3b2dda135624ce2b10b2c80d1c2a0bd
    81 ″ schema:url https://doi.org/10.1007/s00145-015-9226-0
    82 ″ sgo:license sg:explorer/license/
    83 ″ sgo:sdDataset articles
    84 ″ rdf:type schema:ScholarlyArticle
    85 N0073680eb6634f4caacf539c483b0b39 rdf:first sg:person.07776170271.83
    86 ″ rdf:rest N4c69f1c53dd9414e9500a3d3549338ed
    87 N27502fd2ee3e4e368c58fb2343f91b35 schema:volumeNumber 30
    88 ″ rdf:type schema:PublicationVolume
    89 N2a6f1c083bf440c991684fc940e294c6 schema:issueNumber 2
    90 ″ rdf:type schema:PublicationIssue
    91 N4c69f1c53dd9414e9500a3d3549338ed rdf:first sg:person.015120037757.44
    92 ″ rdf:rest rdf:nil
    93 N664d7f60a2f74d3e9b59acb1c157b721 schema:name doi
    94 ″ schema:value 10.1007/s00145-015-9226-0
    95 ″ rdf:type schema:PropertyValue
    96 Nb3b2dda135624ce2b10b2c80d1c2a0bd schema:name Springer Nature - SN SciGraph project
    97 ″ rdf:type schema:Organization
    98 Nc75c97e902fb480099a282a1264b0bb4 schema:name dimensions_id
    99 ″ schema:value pub.1009468991
    100 ″ rdf:type schema:PropertyValue
    101 Nfc10ce25a1fa462c8d40e5ae33acadd7 rdf:first sg:person.012204235441.12
    102 ″ rdf:rest N0073680eb6634f4caacf539c483b0b39
    103 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    104 ″ schema:name Information and Computing Sciences
    105 ″ rdf:type schema:DefinedTerm
    106 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    107 ″ schema:name Computation Theory and Mathematics
    108 ″ rdf:type schema:DefinedTerm
    109 sg:journal.1136278 schema:issn 0933-2790
    110 ″ ″ 1432-1378
    111 ″ schema:name Journal of Cryptology
    112 ″ schema:publisher Springer Nature
    113 ″ rdf:type schema:Periodical
    114 sg:person.012204235441.12 schema:affiliation grid-institutes:grid.13992.30
    115 ″ schema:familyName Komargodski
    116 ″ schema:givenName Ilan
    117 ″ schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012204235441.12
    118 ″ rdf:type schema:Person
    119 sg:person.015120037757.44 schema:affiliation grid-institutes:grid.13992.30
    120 ″ schema:familyName Yogev
    121 ″ schema:givenName Eylon
    122 ″ schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44
    123 ″ rdf:type schema:Person
    124 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
    125 ″ schema:familyName Naor
    126 ″ schema:givenName Moni
    127 ″ schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
    128 ″ rdf:type schema:Person
    129 sg:pub.10.1007/3-540-44647-8_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039594573
    130 ″ ″ https://doi.org/10.1007/3-540-44647-8_1
    131 ″ rdf:type schema:CreativeWork
    132 sg:pub.10.1007/978-3-662-49099-0_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041458690
    133 ″ ″ https://doi.org/10.1007/978-3-662-49099-0_17
    134 ″ rdf:type schema:CreativeWork
    135 sg:pub.10.1007/bf00196774 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003773885
    136 ″ ″ https://doi.org/10.1007/bf00196774
    137 ″ rdf:type schema:CreativeWork
    138 sg:pub.10.1007/bf02620229 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026401336
    139 ″ ″ https://doi.org/10.1007/bf02620229
    140 ″ rdf:type schema:CreativeWork
    141 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Rehovot, Israel
    142 ″ schema:name Weizmann Institute of Science, Rehovot, Israel
    143 ″ rdf:type schema:Organization
     




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

    ...