TY - CHAP
T1 - Streaming Authenticated Data Structures
T2 - Advances in Cryptology – EUROCRYPT 2013
Y1 - 2013
A1 - Charalampos Papamanthou
A1 - Shi, Elaine
A1 - Tamassia, Roberto
A1 - Yi, Ke
ED - Johansson, Thomas
ED - Nguyen, Phong Q.
KW - Algorithm Analysis and Problem Complexity
KW - Data Encryption
KW - Discrete Mathematics in Computer Science
KW - Systems and Data Security
AB - We consider the problem of streaming verifiable computation, where both a verifier and a prover observe a stream of n elements x 1,x 2,…,x n 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 O(logM logn)O(\log M\ log n) 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.
JA - Advances in Cryptology – EUROCRYPT 2013
T3 - Lecture Notes in Computer Science
PB - Springer Berlin Heidelberg
SN - 978-3-642-38347-2, 978-3-642-38348-9
UR - http://link.springer.com/chapter/10.1007/978-3-642-38348-9_22
ER -