Incrementally Verifiable Computation via Incremental PCPs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2019-11-22

AUTHORS

Moni Naor , Omer Paneth , Guy N. Rothblum

ABSTRACT

If I commission a long computation, how can I check that the result is correct without re-doing the computation myself? This is the question that efficient verifiable computation deals with. In this work, we address the issue of verifying the computation as it unfolds. That is, at any intermediate point in the computation, I would like to see a proof that the current state is correct. Ideally, these proofs should be short, non-interactive, and easy to verify. In addition, the proof at each step should be generated efficiently by updating the previous proof, without recomputing the entire proof from scratch. This notion, known as incrementally verifiable computation, was introduced by Valiant [TCC 08] about a decade ago. Existing solutions follow the approach of recursive proof composition and can be based on strong and non-falsifiable cryptographic assumptions (so-called “knowledge assumptions”).In this work, we present a new framework for constructing incrementally verifiable computation schemes in both the publicly verifiable and designated-verifier settings. Our designated-verifier scheme is based on somewhat homomorphic encryption (which can be based on Learning with Errors) and our publicly verifiable scheme is based on the notion of zero-testable homomorphic encryption, which can be constructed from ideal multi-linear maps [Paneth and Rothblum, TCC 17].Our framework is anchored around the new notion of a probabilistically checkable proof (PCP) with incremental local updates. An incrementally updatable PCP proves the correctness of an ongoing computation, where after each computation step, the value of every symbol can be updated locally without reading any other symbol. This update results in a new PCP for the correctness of the next step in the computation. Our primary technical contribution is constructing such an incrementally updatable PCP. We show how to combine updatable PCPs with recently suggested (ordinary) verifiable computation to obtain our results. More... »

PAGES

552-576

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-36033-7_21

DOI

http://dx.doi.org/10.1007/978-3-030-36033-7_21

DIMENSIONS

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


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": "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": "MIT and Northeastern University, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.261112.7", 
          "name": [
            "MIT and Northeastern University, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Paneth", 
        "givenName": "Omer", 
        "id": "sg:person.014073524511.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68"
        ], 
        "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": "Rothblum", 
        "givenName": "Guy N.", 
        "id": "sg:person.014351474277.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351474277.34"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2019-11-22", 
    "datePublishedReg": "2019-11-22", 
    "description": "Abstract\nIf I commission a long computation, how can I check that the result is correct without re-doing the computation myself? This is the question that efficient verifiable computation deals with. In this work, we address the issue of verifying the computation as it unfolds. That is, at any intermediate point in the computation, I would like to see a proof that the current state is correct. Ideally, these proofs should be short, non-interactive, and easy to verify. In addition, the proof at each step should be generated efficiently by updating the previous proof, without recomputing the entire proof from scratch. This notion, known as incrementally verifiable computation, was introduced by Valiant [TCC 08] about a decade ago. Existing solutions follow the approach of recursive proof composition and can be based on strong and non-falsifiable cryptographic assumptions (so-called \u201cknowledge assumptions\u201d).In this work, we present a new framework for constructing incrementally verifiable computation schemes in both the publicly verifiable and designated-verifier settings. Our designated-verifier scheme is based on somewhat homomorphic encryption (which can be based on Learning with Errors) and our publicly verifiable scheme is based on the notion of zero-testable homomorphic encryption, which can be constructed from ideal multi-linear maps [Paneth and Rothblum, TCC 17].Our framework is anchored around the new notion of a probabilistically checkable proof (PCP) with incremental local updates. An incrementally updatable PCP proves the correctness of an ongoing computation, where after each computation step, the value of every symbol can be updated locally without reading any other symbol. This update results in a new PCP for the correctness of the next step in the computation. Our primary technical contribution is constructing such an incrementally updatable PCP. We show how to combine updatable PCPs with recently suggested (ordinary) verifiable computation to obtain our results.", 
    "editor": [
      {
        "familyName": "Hofheinz", 
        "givenName": "Dennis", 
        "type": "Person"
      }, 
      {
        "familyName": "Rosen", 
        "givenName": "Alon", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-36033-7_21", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-36032-0", 
        "978-3-030-36033-7"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "verifiable computation", 
      "homomorphic encryption", 
      "Efficient Verifiable Computation", 
      "recursive proof composition", 
      "verifiable computation scheme", 
      "primary technical contribution", 
      "multi-linear maps", 
      "proof composition", 
      "verifiable scheme", 
      "cryptographic assumptions", 
      "local updates", 
      "computation steps", 
      "checkable proofs", 
      "ongoing computations", 
      "technical contribution", 
      "computation scheme", 
      "encryption", 
      "new framework", 
      "long computations", 
      "computation", 
      "entire proof", 
      "new PCP", 
      "correctness", 
      "scheme", 
      "new notion", 
      "current state", 
      "previous proofs", 
      "framework", 
      "proof", 
      "intermediate points", 
      "next step", 
      "update", 
      "scratch", 
      "Valiant", 
      "step", 
      "symbols", 
      "work", 
      "notion", 
      "maps", 
      "issues", 
      "solution", 
      "results", 
      "point", 
      "assumption", 
      "state", 
      "setting", 
      "contribution", 
      "decades", 
      "questions", 
      "addition", 
      "values", 
      "PCP", 
      "composition", 
      "approach"
    ], 
    "name": "Incrementally Verifiable Computation via Incremental PCPs", 
    "pagination": "552-576", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1122801604"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-36033-7_21"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-36033-7_21", 
      "https://app.dimensions.ai/details/publication/pub.1122801604"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_445.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-36033-7_21"
  }
]
 

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/978-3-030-36033-7_21'

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/978-3-030-36033-7_21'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-36033-7_21'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-36033-7_21'


 

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

136 TRIPLES      23 PREDICATES      79 URIs      72 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-36033-7_21 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nb27168312302478485533e154048c538
4 schema:datePublished 2019-11-22
5 schema:datePublishedReg 2019-11-22
6 schema:description Abstract If I commission a long computation, how can I check that the result is correct without re-doing the computation myself? This is the question that efficient verifiable computation deals with. In this work, we address the issue of verifying the computation as it unfolds. That is, at any intermediate point in the computation, I would like to see a proof that the current state is correct. Ideally, these proofs should be short, non-interactive, and easy to verify. In addition, the proof at each step should be generated efficiently by updating the previous proof, without recomputing the entire proof from scratch. This notion, known as incrementally verifiable computation, was introduced by Valiant [TCC 08] about a decade ago. Existing solutions follow the approach of recursive proof composition and can be based on strong and non-falsifiable cryptographic assumptions (so-called “knowledge assumptions”).In this work, we present a new framework for constructing incrementally verifiable computation schemes in both the publicly verifiable and designated-verifier settings. Our designated-verifier scheme is based on somewhat homomorphic encryption (which can be based on Learning with Errors) and our publicly verifiable scheme is based on the notion of zero-testable homomorphic encryption, which can be constructed from ideal multi-linear maps [Paneth and Rothblum, TCC 17].Our framework is anchored around the new notion of a probabilistically checkable proof (PCP) with incremental local updates. An incrementally updatable PCP proves the correctness of an ongoing computation, where after each computation step, the value of every symbol can be updated locally without reading any other symbol. This update results in a new PCP for the correctness of the next step in the computation. Our primary technical contribution is constructing such an incrementally updatable PCP. We show how to combine updatable PCPs with recently suggested (ordinary) verifiable computation to obtain our results.
7 schema:editor Naabe8fef932b4dc4a80aa2348de92e46
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N86c2b2922ca942adb2020e7ed0ffcd21
12 schema:keywords Efficient Verifiable Computation
13 PCP
14 Valiant
15 addition
16 approach
17 assumption
18 checkable proofs
19 composition
20 computation
21 computation scheme
22 computation steps
23 contribution
24 correctness
25 cryptographic assumptions
26 current state
27 decades
28 encryption
29 entire proof
30 framework
31 homomorphic encryption
32 intermediate points
33 issues
34 local updates
35 long computations
36 maps
37 multi-linear maps
38 new PCP
39 new framework
40 new notion
41 next step
42 notion
43 ongoing computations
44 point
45 previous proofs
46 primary technical contribution
47 proof
48 proof composition
49 questions
50 recursive proof composition
51 results
52 scheme
53 scratch
54 setting
55 solution
56 state
57 step
58 symbols
59 technical contribution
60 update
61 values
62 verifiable computation
63 verifiable computation scheme
64 verifiable scheme
65 work
66 schema:name Incrementally Verifiable Computation via Incremental PCPs
67 schema:pagination 552-576
68 schema:productId N18f799fab29341e7ad578b4b4baaf494
69 N45f148a782b94fbeaf0d680fbe18a9e7
70 schema:publisher Nf9f7dbdf890a4184bc332fb335aaaceb
71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1122801604
72 https://doi.org/10.1007/978-3-030-36033-7_21
73 schema:sdDatePublished 2022-05-20T07:48
74 schema:sdLicense https://scigraph.springernature.com/explorer/license/
75 schema:sdPublisher N6021ab11882240c0b40f02e47e921ecc
76 schema:url https://doi.org/10.1007/978-3-030-36033-7_21
77 sgo:license sg:explorer/license/
78 sgo:sdDataset chapters
79 rdf:type schema:Chapter
80 N18f799fab29341e7ad578b4b4baaf494 schema:name dimensions_id
81 schema:value pub.1122801604
82 rdf:type schema:PropertyValue
83 N45f148a782b94fbeaf0d680fbe18a9e7 schema:name doi
84 schema:value 10.1007/978-3-030-36033-7_21
85 rdf:type schema:PropertyValue
86 N6021ab11882240c0b40f02e47e921ecc schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 N7eea48bdecf5496baf1e55999873b994 schema:familyName Rosen
89 schema:givenName Alon
90 rdf:type schema:Person
91 N84a1e6443e90412f86771ca8050e476b rdf:first N7eea48bdecf5496baf1e55999873b994
92 rdf:rest rdf:nil
93 N86c2b2922ca942adb2020e7ed0ffcd21 schema:isbn 978-3-030-36032-0
94 978-3-030-36033-7
95 schema:name Theory of Cryptography
96 rdf:type schema:Book
97 Naabe8fef932b4dc4a80aa2348de92e46 rdf:first Nf8d2d34493064dca94b1c00b7bb95cbe
98 rdf:rest N84a1e6443e90412f86771ca8050e476b
99 Nb27168312302478485533e154048c538 rdf:first sg:person.07776170271.83
100 rdf:rest Nca1394f784ce4f1c9b172a957d8fd080
101 Nb9be80e041cb4dc38ab6910b1cbf8f46 rdf:first sg:person.014351474277.34
102 rdf:rest rdf:nil
103 Nca1394f784ce4f1c9b172a957d8fd080 rdf:first sg:person.014073524511.68
104 rdf:rest Nb9be80e041cb4dc38ab6910b1cbf8f46
105 Nf8d2d34493064dca94b1c00b7bb95cbe schema:familyName Hofheinz
106 schema:givenName Dennis
107 rdf:type schema:Person
108 Nf9f7dbdf890a4184bc332fb335aaaceb schema:name Springer Nature
109 rdf:type schema:Organisation
110 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
111 schema:name Information and Computing Sciences
112 rdf:type schema:DefinedTerm
113 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
114 schema:name Computation Theory and Mathematics
115 rdf:type schema:DefinedTerm
116 sg:person.014073524511.68 schema:affiliation grid-institutes:grid.261112.7
117 schema:familyName Paneth
118 schema:givenName Omer
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68
120 rdf:type schema:Person
121 sg:person.014351474277.34 schema:affiliation grid-institutes:grid.13992.30
122 schema:familyName Rothblum
123 schema:givenName Guy N.
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351474277.34
125 rdf:type schema:Person
126 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
127 schema:familyName Naor
128 schema:givenName Moni
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
130 rdf:type schema:Person
131 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Rehovot, Israel
132 schema:name Weizmann Institute of Science, Rehovot, Israel
133 rdf:type schema:Organization
134 grid-institutes:grid.261112.7 schema:alternateName MIT and Northeastern University, Cambridge, USA
135 schema:name MIT and Northeastern University, Cambridge, USA
136 rdf:type schema:Organization
 




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


...