Streaming Authenticated Data Structures View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Charalampos Papamanthou , Elaine Shi , Roberto Tamassia , Ke Yi

ABSTRACT

We consider the problem of streaming verifiable computation, where both a verifier and a prover observe a stream of n elements x1,x2,…,xn and the verifier can later delegate some computation over the stream to the prover. The prover must return the output of the computation, along with a cryptographic proof to be used for verifying the correctness of the output. Due to the nature of the streaming setting, the verifier can only keep small local state (e.g., logarithmic) which must be updatable in a streaming manner and with no interaction with the prover. Such constraints make the problem particularly challenging and rule out applying existing verifiable computation schemes.We propose streaming authenticated data structures, a model that enables efficient verification of data structure queries on a stream. Compared to previous work, we achieve an exponential improvement in the prover’s running time: While previous solutions have linear prover complexity (in the size of the stream), even for queries executing in sublinear time (e.g., set membership), we propose a scheme with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\log M\ log n)$\end{document} prover complexity, where n is the size of the stream and M is the size of the universe of elements. Our schemes support a series of expressive queries, such as (non-)membership, successor, range search and frequency queries, over an ordered universe and even in higher dimensions. The central idea of our construction is a new authentication tree, called generalized hash tree. We instantiate our generalized hash tree with a hash function based on lattices assumptions, showing that it enjoys suitable algebraic properties that traditional Merkle trees lack. We exploit such properties to achieve our results. More... »

PAGES

353-370

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-38348-9_22

DOI

http://dx.doi.org/10.1007/978-3-642-38348-9_22

DIMENSIONS

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


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"
      }, 
      {
        "affiliation": {
          "alternateName": "The Hong Kong University of Science and Technology, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.24515.37", 
          "name": [
            "The Hong Kong University of Science and Technology, Hong Kong"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yi", 
        "givenName": "Ke", 
        "id": "sg:person.014230716623.94", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014230716623.94"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We consider the problem of streaming verifiable computation, where both a verifier and a prover observe a stream of n elements x1,x2,\u2026,xn and the verifier can later delegate some computation over the stream to the prover. The prover must return the output of the computation, along with a cryptographic proof to be used for verifying the correctness of the output. Due to the nature of the streaming setting, the verifier can only keep small local state (e.g., logarithmic) which must be updatable in a streaming manner and with no interaction with the prover. Such constraints make the problem particularly challenging and rule out applying existing verifiable computation schemes.We propose streaming authenticated data structures, a model that enables efficient verification of data structure queries on a stream. Compared to previous work, we achieve an exponential improvement in the prover\u2019s running time: While previous solutions have linear prover complexity (in the size of the stream), even for queries executing in sublinear time (e.g., set membership), we propose a scheme with \\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}$O(\\log M\\ log n)$\\end{document} prover complexity, where n is the size of the stream and M is the size of the universe of elements. Our schemes support a series of expressive queries, such as (non-)membership, successor, range search and frequency queries, over an ordered universe and even in higher dimensions. The central idea of our construction is a new authentication tree, called generalized hash tree. We instantiate our generalized hash tree with a hash function based on lattices assumptions, showing that it enjoys suitable algebraic properties that traditional Merkle trees lack. We exploit such properties to achieve our results.", 
    "editor": [
      {
        "familyName": "Johansson", 
        "givenName": "Thomas", 
        "type": "Person"
      }, 
      {
        "familyName": "Nguyen", 
        "givenName": "Phong Q.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-38348-9_22", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-38347-2", 
        "978-3-642-38348-9"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2013", 
      "type": "Book"
    }, 
    "keywords": [
      "hash tree", 
      "data structure", 
      "running time", 
      "verifiable computation scheme", 
      "Authenticated Data Structures", 
      "universe of elements", 
      "expressive queries", 
      "cryptographic proofs", 
      "verifiable computation", 
      "structure query", 
      "efficient verification", 
      "authentication tree", 
      "Merkle tree", 
      "range search", 
      "streaming setting", 
      "hash functions", 
      "queries", 
      "frequency queries", 
      "sublinear time", 
      "provers", 
      "previous solutions", 
      "verifier", 
      "lattice assumptions", 
      "computation scheme", 
      "exponential improvement", 
      "such constraints", 
      "computation", 
      "scheme", 
      "higher dimensions", 
      "central idea", 
      "complexity", 
      "previous work", 
      "streams", 
      "algebraic properties", 
      "local state", 
      "correctness", 
      "trees", 
      "verification", 
      "ordered universe", 
      "such properties", 
      "constraints", 
      "output", 
      "search", 
      "proof", 
      "idea", 
      "time", 
      "solution", 
      "work", 
      "elements", 
      "construction", 
      "model", 
      "improvement", 
      "successor", 
      "manner", 
      "assumption", 
      "size", 
      "structure", 
      "results", 
      "dimensions", 
      "state", 
      "setting", 
      "universe", 
      "function", 
      "nature", 
      "interaction", 
      "properties", 
      "series", 
      "problem", 
      "small local state", 
      "data structure queries", 
      "prover\u2019s running time", 
      "new authentication tree", 
      "generalized hash tree", 
      "suitable algebraic properties", 
      "traditional Merkle trees"
    ], 
    "name": "Streaming Authenticated Data Structures", 
    "pagination": "353-370", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038140112"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-38348-9_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-38348-9_22", 
      "https://app.dimensions.ai/details/publication/pub.1038140112"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_202.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-38348-9_22"
  }
]
 

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-38348-9_22'

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-38348-9_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38348-9_22'

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-38348-9_22'


 

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

170 TRIPLES      23 PREDICATES      101 URIs      94 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-38348-9_22 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5ef51bf9b786405096801ceb32e151d4
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We consider the problem of streaming verifiable computation, where both a verifier and a prover observe a stream of n elements x1,x2,…,xn and the verifier can later delegate some computation over the stream to the prover. The prover must return the output of the computation, along with a cryptographic proof to be used for verifying the correctness of the output. Due to the nature of the streaming setting, the verifier can only keep small local state (e.g., logarithmic) which must be updatable in a streaming manner and with no interaction with the prover. Such constraints make the problem particularly challenging and rule out applying existing verifiable computation schemes.We propose streaming authenticated data structures, a model that enables efficient verification of data structure queries on a stream. Compared to previous work, we achieve an exponential improvement in the prover’s running time: While previous solutions have linear prover complexity (in the size of the stream), even for queries executing in sublinear time (e.g., set membership), we propose a scheme with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\log M\ log n)$\end{document} prover complexity, where n is the size of the stream and M is the size of the universe of elements. Our schemes support a series of expressive queries, such as (non-)membership, successor, range search and frequency queries, over an ordered universe and even in higher dimensions. The central idea of our construction is a new authentication tree, called generalized hash tree. We instantiate our generalized hash tree with a hash function based on lattices assumptions, showing that it enjoys suitable algebraic properties that traditional Merkle trees lack. We exploit such properties to achieve our results.
7 schema:editor N4dc50707fb3d48928bf73a14b7de460d
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N9c4d45c07d5744e797bdaa645c14727e
12 schema:keywords Authenticated Data Structures
13 Merkle tree
14 algebraic properties
15 assumption
16 authentication tree
17 central idea
18 complexity
19 computation
20 computation scheme
21 constraints
22 construction
23 correctness
24 cryptographic proofs
25 data structure
26 data structure queries
27 dimensions
28 efficient verification
29 elements
30 exponential improvement
31 expressive queries
32 frequency queries
33 function
34 generalized hash tree
35 hash functions
36 hash tree
37 higher dimensions
38 idea
39 improvement
40 interaction
41 lattice assumptions
42 local state
43 manner
44 model
45 nature
46 new authentication tree
47 ordered universe
48 output
49 previous solutions
50 previous work
51 problem
52 proof
53 properties
54 provers
55 prover’s running time
56 queries
57 range search
58 results
59 running time
60 scheme
61 search
62 series
63 setting
64 size
65 small local state
66 solution
67 state
68 streaming setting
69 streams
70 structure
71 structure query
72 sublinear time
73 successor
74 such constraints
75 such properties
76 suitable algebraic properties
77 time
78 traditional Merkle trees
79 trees
80 universe
81 universe of elements
82 verifiable computation
83 verifiable computation scheme
84 verification
85 verifier
86 work
87 schema:name Streaming Authenticated Data Structures
88 schema:pagination 353-370
89 schema:productId N675bc7f387354713ac2cc8043dd92b6e
90 N73abf51e05484b11bbf04b531cbc6be1
91 schema:publisher N19ef4b26c8924deda44ed9e519269d74
92 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038140112
93 https://doi.org/10.1007/978-3-642-38348-9_22
94 schema:sdDatePublished 2021-11-01T18:50
95 schema:sdLicense https://scigraph.springernature.com/explorer/license/
96 schema:sdPublisher N3cf35980b2864d2484f7edbb903615e0
97 schema:url https://doi.org/10.1007/978-3-642-38348-9_22
98 sgo:license sg:explorer/license/
99 sgo:sdDataset chapters
100 rdf:type schema:Chapter
101 N19ef4b26c8924deda44ed9e519269d74 schema:name Springer Nature
102 rdf:type schema:Organisation
103 N1ef5752de95645c8b983b12c17ded7be rdf:first sg:person.0674326220.33
104 rdf:rest Nbba6a2da66b7481b992b012a6643e8e8
105 N3cf35980b2864d2484f7edbb903615e0 schema:name Springer Nature - SN SciGraph project
106 rdf:type schema:Organization
107 N4dc50707fb3d48928bf73a14b7de460d rdf:first Ncc319017c8444dfea775dd72e339e823
108 rdf:rest Nc787281cd7f24f17a9b9d0b5acc61154
109 N5ef51bf9b786405096801ceb32e151d4 rdf:first sg:person.010450677547.30
110 rdf:rest Na5602ff808df4b9e9b9bb7a657cb7d11
111 N675bc7f387354713ac2cc8043dd92b6e schema:name doi
112 schema:value 10.1007/978-3-642-38348-9_22
113 rdf:type schema:PropertyValue
114 N73abf51e05484b11bbf04b531cbc6be1 schema:name dimensions_id
115 schema:value pub.1038140112
116 rdf:type schema:PropertyValue
117 N9c4d45c07d5744e797bdaa645c14727e schema:isbn 978-3-642-38347-2
118 978-3-642-38348-9
119 schema:name Advances in Cryptology – EUROCRYPT 2013
120 rdf:type schema:Book
121 Na5602ff808df4b9e9b9bb7a657cb7d11 rdf:first sg:person.014706274717.52
122 rdf:rest N1ef5752de95645c8b983b12c17ded7be
123 Nbba6a2da66b7481b992b012a6643e8e8 rdf:first sg:person.014230716623.94
124 rdf:rest rdf:nil
125 Nc787281cd7f24f17a9b9d0b5acc61154 rdf:first Nd92631994a9e4fa8bf0ec38e61875159
126 rdf:rest rdf:nil
127 Ncc319017c8444dfea775dd72e339e823 schema:familyName Johansson
128 schema:givenName Thomas
129 rdf:type schema:Person
130 Nd92631994a9e4fa8bf0ec38e61875159 schema:familyName Nguyen
131 schema:givenName Phong Q.
132 rdf:type schema:Person
133 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
134 schema:name Information and Computing Sciences
135 rdf:type schema:DefinedTerm
136 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
137 schema:name Computation Theory and Mathematics
138 rdf:type schema:DefinedTerm
139 sg:person.010450677547.30 schema:affiliation grid-institutes:grid.47840.3f
140 schema:familyName Papamanthou
141 schema:givenName Charalampos
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450677547.30
143 rdf:type schema:Person
144 sg:person.014230716623.94 schema:affiliation grid-institutes:grid.24515.37
145 schema:familyName Yi
146 schema:givenName Ke
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014230716623.94
148 rdf:type schema:Person
149 sg:person.014706274717.52 schema:affiliation grid-institutes:grid.410443.6
150 schema:familyName Shi
151 schema:givenName Elaine
152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52
153 rdf:type schema:Person
154 sg:person.0674326220.33 schema:affiliation grid-institutes:grid.40263.33
155 schema:familyName Tamassia
156 schema:givenName Roberto
157 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33
158 rdf:type schema:Person
159 grid-institutes:grid.24515.37 schema:alternateName The Hong Kong University of Science and Technology, Hong Kong
160 schema:name The Hong Kong University of Science and Technology, Hong Kong
161 rdf:type schema:Organization
162 grid-institutes:grid.40263.33 schema:alternateName Brown University, USA
163 schema:name Brown University, USA
164 rdf:type schema:Organization
165 grid-institutes:grid.410443.6 schema:alternateName University of Maryland, USA
166 schema:name University of Maryland, USA
167 rdf:type schema:Organization
168 grid-institutes:grid.47840.3f schema:alternateName UC Berkeley, USA
169 schema:name UC Berkeley, USA
170 rdf:type schema:Organization
 




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


...