Signatures of Correct Computation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Charalampos Papamanthou , Elaine Shi , Roberto Tamassia

ABSTRACT

We introduce Signatures of Correct Computation (SCC), a new model for verifying dynamic computations in cloud settings. In the SCC model, a trusted source outsources a function f to an untrusted server, along with a public key for that function (to be used during verification). The server can then produce a succinct signature σ vouching for the correctness of the computation of f, i.e., that some result v is indeed the correct outcome of the function f evaluated on some point a. There are two crucial performance properties that we want to guarantee in an SCC construction: (1) verifying the signature should take asymptotically less time than evaluating the function f; and (2) the public key should be efficiently updated whenever the function changes.We construct SCC schemes (satisfying the above two properties) supporting expressive manipulations over multivariate polynomials, such as polynomial evaluation and differentiation. Our constructions are adaptively secure in the random oracle model and achieve optimal updates, i.e., the function’s public key can be updated in time proportional to the number of updated coefficients, without performing a linear-time computation (in the size of the polynomial).We also show that signatures of correct computation imply Publicly Verifiable Computation (PVC), a model recently introduced in several concurrent and independent works. Roughly speaking, in the SCC model, any client can verify the signature σ and be convinced of some computation result, whereas in the PVC model only the client that issued a query (or anyone who trusts this client) can verify that the server returned a valid signature (proof) for the answer to the query. Our techniques can be readily adapted to construct PVC schemes with adaptive security, efficient updates and without the random oracle model. More... »

PAGES

222-242

Book

TITLE

Theory of Cryptography

ISBN

978-3-642-36593-5
978-3-642-36594-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-36594-2_13

DOI

http://dx.doi.org/10.1007/978-3-642-36594-2_13

DIMENSIONS

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


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": "UC Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "UC Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papamanthou", 
        "givenName": "Charalampos", 
        "id": "sg:person.010450677547.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450677547.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Maryland, USA", 
          "id": "http://www.grid.ac/institutes/grid.410443.6", 
          "name": [
            "University of Maryland, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shi", 
        "givenName": "Elaine", 
        "id": "sg:person.014706274717.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Brown University, USA", 
          "id": "http://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Brown University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tamassia", 
        "givenName": "Roberto", 
        "id": "sg:person.0674326220.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We introduce Signatures of Correct Computation (SCC), a new model for verifying dynamic computations in cloud settings. In the SCC model, a trusted source outsources a function f to an untrusted server, along with a public key for that function (to be used during verification). The server can then produce a succinct signature \u03c3 vouching for the correctness of the computation of f, i.e., that some result v is indeed the correct outcome of the function f evaluated on some point a. There are two crucial performance properties that we want to guarantee in an SCC construction: (1)\u00a0verifying the signature should take asymptotically less time than evaluating the function f; and (2)\u00a0the public key should be efficiently updated whenever the function changes.We construct SCC schemes (satisfying the above two properties) supporting expressive manipulations over multivariate polynomials, such as polynomial evaluation and differentiation. Our constructions are adaptively secure in the random oracle model and achieve optimal updates, i.e., the function\u2019s public key can be updated in time proportional to the number of updated coefficients, without performing a linear-time computation (in the size of the polynomial).We also show that signatures of correct computation imply Publicly Verifiable Computation (PVC), a model recently introduced in several concurrent and independent works. Roughly speaking, in the SCC model, any client can verify the signature \u03c3 and be convinced of some computation result, whereas in the PVC model only the client that issued a query (or anyone who trusts this client) can verify that the server returned a valid signature (proof) for the answer to the query. Our techniques can be readily adapted to construct PVC schemes with adaptive security, efficient updates and without the random oracle model.", 
    "editor": [
      {
        "familyName": "Sahai", 
        "givenName": "Amit", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-36594-2_13", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-36593-5", 
        "978-3-642-36594-2"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "random oracle model", 
      "public key", 
      "oracle model", 
      "correct computation", 
      "linear-time computation", 
      "untrusted server", 
      "verifiable computation", 
      "cloud setting", 
      "adaptive security", 
      "PVC scheme", 
      "optimal update", 
      "SCC scheme", 
      "valid signature", 
      "server", 
      "polynomial evaluation", 
      "queries", 
      "computation", 
      "dynamics computations", 
      "multivariate polynomials", 
      "computation results", 
      "key", 
      "scheme", 
      "correct outcome", 
      "clients", 
      "less time", 
      "performance properties", 
      "security", 
      "correctness", 
      "independent work", 
      "new model", 
      "model", 
      "update", 
      "signatures", 
      "function f", 
      "PVC model", 
      "construction", 
      "technique", 
      "time", 
      "work", 
      "answers", 
      "manipulation", 
      "polynomials", 
      "evaluation", 
      "number", 
      "function", 
      "results", 
      "setting", 
      "source", 
      "signature \u03a3", 
      "coefficient", 
      "properties", 
      "point A.", 
      "SCC model", 
      "outcomes", 
      "differentiation", 
      "A.", 
      "succinct signature \u03c3", 
      "result v", 
      "crucial performance properties", 
      "SCC construction", 
      "expressive manipulations", 
      "function\u2019s public key", 
      "Publicly Verifiable Computation"
    ], 
    "name": "Signatures of Correct Computation", 
    "pagination": "222-242", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027409438"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-36594-2_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-36594-2_13", 
      "https://app.dimensions.ai/details/publication/pub.1027409438"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:10", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_431.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-36594-2_13"
  }
]
 

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-642-36594-2_13'

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-642-36594-2_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-36594-2_13'

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-642-36594-2_13'


 

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

143 TRIPLES      23 PREDICATES      89 URIs      82 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-36594-2_13 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N72d3c9fe26b6436a87df4151f9404890
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We introduce Signatures of Correct Computation (SCC), a new model for verifying dynamic computations in cloud settings. In the SCC model, a trusted source outsources a function f to an untrusted server, along with a public key for that function (to be used during verification). The server can then produce a succinct signature σ vouching for the correctness of the computation of f, i.e., that some result v is indeed the correct outcome of the function f evaluated on some point a. There are two crucial performance properties that we want to guarantee in an SCC construction: (1) verifying the signature should take asymptotically less time than evaluating the function f; and (2) the public key should be efficiently updated whenever the function changes.We construct SCC schemes (satisfying the above two properties) supporting expressive manipulations over multivariate polynomials, such as polynomial evaluation and differentiation. Our constructions are adaptively secure in the random oracle model and achieve optimal updates, i.e., the function’s public key can be updated in time proportional to the number of updated coefficients, without performing a linear-time computation (in the size of the polynomial).We also show that signatures of correct computation imply Publicly Verifiable Computation (PVC), a model recently introduced in several concurrent and independent works. Roughly speaking, in the SCC model, any client can verify the signature σ and be convinced of some computation result, whereas in the PVC model only the client that issued a query (or anyone who trusts this client) can verify that the server returned a valid signature (proof) for the answer to the query. Our techniques can be readily adapted to construct PVC schemes with adaptive security, efficient updates and without the random oracle model.
7 schema:editor N722b3ba2949341fe8c0f2f863c550ee6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3c1b6d565bda4701a5551848ceeeeb33
12 schema:keywords A.
13 PVC model
14 PVC scheme
15 Publicly Verifiable Computation
16 SCC construction
17 SCC model
18 SCC scheme
19 adaptive security
20 answers
21 clients
22 cloud setting
23 coefficient
24 computation
25 computation results
26 construction
27 correct computation
28 correct outcome
29 correctness
30 crucial performance properties
31 differentiation
32 dynamics computations
33 evaluation
34 expressive manipulations
35 function
36 function f
37 function’s public key
38 independent work
39 key
40 less time
41 linear-time computation
42 manipulation
43 model
44 multivariate polynomials
45 new model
46 number
47 optimal update
48 oracle model
49 outcomes
50 performance properties
51 point A.
52 polynomial evaluation
53 polynomials
54 properties
55 public key
56 queries
57 random oracle model
58 result v
59 results
60 scheme
61 security
62 server
63 setting
64 signature Σ
65 signatures
66 source
67 succinct signature σ
68 technique
69 time
70 untrusted server
71 update
72 valid signature
73 verifiable computation
74 work
75 schema:name Signatures of Correct Computation
76 schema:pagination 222-242
77 schema:productId N55112b91b5cc4806acd644acbbccef32
78 Nd3e5345e932c4f8e80a5202b48da5e1f
79 schema:publisher N1f18fbcacd5a4d33b6b7a4c2791bcece
80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027409438
81 https://doi.org/10.1007/978-3-642-36594-2_13
82 schema:sdDatePublished 2021-12-01T20:10
83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
84 schema:sdPublisher N70dccb37e6c04be5a6fa6b0bf7ea8990
85 schema:url https://doi.org/10.1007/978-3-642-36594-2_13
86 sgo:license sg:explorer/license/
87 sgo:sdDataset chapters
88 rdf:type schema:Chapter
89 N1f18fbcacd5a4d33b6b7a4c2791bcece schema:name Springer Nature
90 rdf:type schema:Organisation
91 N3c1b6d565bda4701a5551848ceeeeb33 schema:isbn 978-3-642-36593-5
92 978-3-642-36594-2
93 schema:name Theory of Cryptography
94 rdf:type schema:Book
95 N55112b91b5cc4806acd644acbbccef32 schema:name doi
96 schema:value 10.1007/978-3-642-36594-2_13
97 rdf:type schema:PropertyValue
98 N70dccb37e6c04be5a6fa6b0bf7ea8990 schema:name Springer Nature - SN SciGraph project
99 rdf:type schema:Organization
100 N722b3ba2949341fe8c0f2f863c550ee6 rdf:first Nafc4e3dd5f8448a299cdcebd4a34fc39
101 rdf:rest rdf:nil
102 N72d3c9fe26b6436a87df4151f9404890 rdf:first sg:person.010450677547.30
103 rdf:rest Nec01174fae954eab8804cebf4cc962e4
104 Nafc4e3dd5f8448a299cdcebd4a34fc39 schema:familyName Sahai
105 schema:givenName Amit
106 rdf:type schema:Person
107 Nd3e5345e932c4f8e80a5202b48da5e1f schema:name dimensions_id
108 schema:value pub.1027409438
109 rdf:type schema:PropertyValue
110 Nea423e55ed4e47e2ba07409b3bd848b8 rdf:first sg:person.0674326220.33
111 rdf:rest rdf:nil
112 Nec01174fae954eab8804cebf4cc962e4 rdf:first sg:person.014706274717.52
113 rdf:rest Nea423e55ed4e47e2ba07409b3bd848b8
114 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
115 schema:name Information and Computing Sciences
116 rdf:type schema:DefinedTerm
117 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
118 schema:name Computation Theory and Mathematics
119 rdf:type schema:DefinedTerm
120 sg:person.010450677547.30 schema:affiliation grid-institutes:grid.47840.3f
121 schema:familyName Papamanthou
122 schema:givenName Charalampos
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450677547.30
124 rdf:type schema:Person
125 sg:person.014706274717.52 schema:affiliation grid-institutes:grid.410443.6
126 schema:familyName Shi
127 schema:givenName Elaine
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52
129 rdf:type schema:Person
130 sg:person.0674326220.33 schema:affiliation grid-institutes:grid.40263.33
131 schema:familyName Tamassia
132 schema:givenName Roberto
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33
134 rdf:type schema:Person
135 grid-institutes:grid.40263.33 schema:alternateName Brown University, USA
136 schema:name Brown University, USA
137 rdf:type schema:Organization
138 grid-institutes:grid.410443.6 schema:alternateName University of Maryland, USA
139 schema:name University of Maryland, USA
140 rdf:type schema:Organization
141 grid-institutes:grid.47840.3f schema:alternateName UC Berkeley, USA
142 schema:name UC Berkeley, USA
143 rdf:type schema:Organization
 




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


...