Definitions and properties of zero-knowledge proof systems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1994-12

AUTHORS

Oded Goldreich, Yair Oren

ABSTRACT

In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary-input zero-knowledge and blackbox-simulation zero-knowledge. We explain why auxiliary-input zero-knowledge is a definition more suitable for cryptographic applications than the original [GMR1] definition. In particular, we show that any protocol solely composed of subprotocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackbox-simulation zero-knowledge implies auxiliary-input zero-knowledge (which in turn implies the [GMR1] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e., we proved zero-knowledge using blackbox-simulation of the verifier). As a result, all known zero-knowledge proof systems are shown to be auxiliary-input zero-knowledge and can be used for cryptographic applications such as those in [GMW2].We demonstrate the triviality of certain classes of zero-knowledge proof systems, in the sense that only languages in BPP have zero-knowledge proofs of these classes. In particular, we show that any language having a Las Vegas zero-knowledge proof system necessarily belongs to RP. We show that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of (nontrivial) auxiliary-input zero-knowledge proofs. More... »

PAGES

1-32

References to SciGraph publications

  • 1988. Direct Minimum-Knowledge Computations (Extended Abstract) in ADVANCES IN CRYPTOLOGY — CRYPTO ’87
  • 1990. On the composition of zero-knowledge proof systems in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf00195207

    DOI

    http://dx.doi.org/10.1007/bf00195207

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, Technion, Haifa, Israel", 
              "id": "http://www.grid.ac/institutes/grid.6451.6", 
              "name": [
                "Department of Computer Science, Technion, Haifa, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Goldreich", 
            "givenName": "Oded", 
            "id": "sg:person.012050724555.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012050724555.27"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, Technion, Haifa, Israel", 
              "id": "http://www.grid.ac/institutes/grid.6451.6", 
              "name": [
                "Department of Computer Science, Technion, Haifa, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Oren", 
            "givenName": "Yair", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-48184-2_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051003216", 
              "https://doi.org/10.1007/3-540-48184-2_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0032038", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022820392", 
              "https://doi.org/10.1007/bfb0032038"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1994-12", 
        "datePublishedReg": "1994-12-01", 
        "description": "In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary-input zero-knowledge and blackbox-simulation zero-knowledge. We explain why auxiliary-input zero-knowledge is a definition more suitable for cryptographic applications than the original [GMR1] definition. In particular, we show that any protocol solely composed of subprotocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackbox-simulation zero-knowledge implies auxiliary-input zero-knowledge (which in turn implies the [GMR1] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e., we proved zero-knowledge using blackbox-simulation of the verifier). As a result, all known zero-knowledge proof systems are shown to be auxiliary-input zero-knowledge and can be used for cryptographic applications such as those in [GMW2].We demonstrate the triviality of certain classes of zero-knowledge proof systems, in the sense that only languages in BPP have zero-knowledge proofs of these classes. In particular, we show that any language having a Las Vegas zero-knowledge proof system necessarily belongs to RP. We show that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of (nontrivial) auxiliary-input zero-knowledge proofs.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf00195207", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136278", 
            "issn": [
              "0933-2790", 
              "1432-1378"
            ], 
            "name": "Journal of Cryptology", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "7"
          }
        ], 
        "keywords": [
          "zero-knowledge proof system", 
          "zero-knowledge proofs", 
          "zero-knowledge", 
          "proof system", 
          "cryptographic applications", 
          "language", 
          "verifier", 
          "Goldwasser", 
          "Rackoff", 
          "Micali", 
          "proof", 
          "only language", 
          "subprotocol", 
          "system", 
          "applications", 
          "essential properties", 
          "BPP", 
          "original definition", 
          "definition", 
          "certain class", 
          "protocol", 
          "randomness", 
          "class", 
          "Las Vegas", 
          "Vegas", 
          "notion", 
          "sense", 
          "results", 
          "fact", 
          "interaction", 
          "properties", 
          "triviality", 
          "RP", 
          "nontriviality", 
          "paper"
        ], 
        "name": "Definitions and properties of zero-knowledge proof systems", 
        "pagination": "1-32", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1051079135"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf00195207"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf00195207", 
          "https://app.dimensions.ai/details/publication/pub.1051079135"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-08-04T16:51", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/article/article_236.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf00195207"
      }
    ]
     

    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/bf00195207'

    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/bf00195207'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf00195207'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf00195207'


     

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

    106 TRIPLES      21 PREDICATES      62 URIs      52 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf00195207 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N8f147faed5e243f6a4ffa6672006f8a9
    4 schema:citation sg:pub.10.1007/3-540-48184-2_4
    5 sg:pub.10.1007/bfb0032038
    6 schema:datePublished 1994-12
    7 schema:datePublishedReg 1994-12-01
    8 schema:description In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary-input zero-knowledge and blackbox-simulation zero-knowledge. We explain why auxiliary-input zero-knowledge is a definition more suitable for cryptographic applications than the original [GMR1] definition. In particular, we show that any protocol solely composed of subprotocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackbox-simulation zero-knowledge implies auxiliary-input zero-knowledge (which in turn implies the [GMR1] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e., we proved zero-knowledge using blackbox-simulation of the verifier). As a result, all known zero-knowledge proof systems are shown to be auxiliary-input zero-knowledge and can be used for cryptographic applications such as those in [GMW2].We demonstrate the triviality of certain classes of zero-knowledge proof systems, in the sense that only languages in BPP have zero-knowledge proofs of these classes. In particular, we show that any language having a Las Vegas zero-knowledge proof system necessarily belongs to RP. We show that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of (nontrivial) auxiliary-input zero-knowledge proofs.
    9 schema:genre article
    10 schema:isAccessibleForFree false
    11 schema:isPartOf Ne9752a338be747169cd06743041aea18
    12 Nfa759bdf88a74d4298dbfeb7a6e059a7
    13 sg:journal.1136278
    14 schema:keywords BPP
    15 Goldwasser
    16 Las Vegas
    17 Micali
    18 RP
    19 Rackoff
    20 Vegas
    21 applications
    22 certain class
    23 class
    24 cryptographic applications
    25 definition
    26 essential properties
    27 fact
    28 interaction
    29 language
    30 nontriviality
    31 notion
    32 only language
    33 original definition
    34 paper
    35 proof
    36 proof system
    37 properties
    38 protocol
    39 randomness
    40 results
    41 sense
    42 subprotocol
    43 system
    44 triviality
    45 verifier
    46 zero-knowledge
    47 zero-knowledge proof system
    48 zero-knowledge proofs
    49 schema:name Definitions and properties of zero-knowledge proof systems
    50 schema:pagination 1-32
    51 schema:productId Naeff368b24ee4616923b2db955e78ced
    52 Neaa22038ae4749a49ac92b05562a1f2e
    53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051079135
    54 https://doi.org/10.1007/bf00195207
    55 schema:sdDatePublished 2022-08-04T16:51
    56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    57 schema:sdPublisher N8732da4263e846dcae679e2ebda817de
    58 schema:url https://doi.org/10.1007/bf00195207
    59 sgo:license sg:explorer/license/
    60 sgo:sdDataset articles
    61 rdf:type schema:ScholarlyArticle
    62 N8732da4263e846dcae679e2ebda817de schema:name Springer Nature - SN SciGraph project
    63 rdf:type schema:Organization
    64 N8f147faed5e243f6a4ffa6672006f8a9 rdf:first sg:person.012050724555.27
    65 rdf:rest Ndce7d5085c55430daeb46f2f7466094a
    66 Naeff368b24ee4616923b2db955e78ced schema:name dimensions_id
    67 schema:value pub.1051079135
    68 rdf:type schema:PropertyValue
    69 Ndce7d5085c55430daeb46f2f7466094a rdf:first Ne6f377604bf7440fb842446fb1d6d89b
    70 rdf:rest rdf:nil
    71 Ne6f377604bf7440fb842446fb1d6d89b schema:affiliation grid-institutes:grid.6451.6
    72 schema:familyName Oren
    73 schema:givenName Yair
    74 rdf:type schema:Person
    75 Ne9752a338be747169cd06743041aea18 schema:volumeNumber 7
    76 rdf:type schema:PublicationVolume
    77 Neaa22038ae4749a49ac92b05562a1f2e schema:name doi
    78 schema:value 10.1007/bf00195207
    79 rdf:type schema:PropertyValue
    80 Nfa759bdf88a74d4298dbfeb7a6e059a7 schema:issueNumber 1
    81 rdf:type schema:PublicationIssue
    82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Information and Computing Sciences
    84 rdf:type schema:DefinedTerm
    85 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Artificial Intelligence and Image Processing
    87 rdf:type schema:DefinedTerm
    88 sg:journal.1136278 schema:issn 0933-2790
    89 1432-1378
    90 schema:name Journal of Cryptology
    91 schema:publisher Springer Nature
    92 rdf:type schema:Periodical
    93 sg:person.012050724555.27 schema:affiliation grid-institutes:grid.6451.6
    94 schema:familyName Goldreich
    95 schema:givenName Oded
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012050724555.27
    97 rdf:type schema:Person
    98 sg:pub.10.1007/3-540-48184-2_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051003216
    99 https://doi.org/10.1007/3-540-48184-2_4
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/bfb0032038 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022820392
    102 https://doi.org/10.1007/bfb0032038
    103 rdf:type schema:CreativeWork
    104 grid-institutes:grid.6451.6 schema:alternateName Department of Computer Science, Technion, Haifa, Israel
    105 schema:name Department of Computer Science, Technion, Haifa, Israel
    106 rdf:type schema:Organization
     




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


    ...