Streaming authenticated data structures: Abstraction and implementation

Yi Qian, Yupeng Zhang, Xi Chen, Charalampos Papamanthou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the setting of streaming verifiable computation, a verifier and a prover observe a stream of n elements x1; x2; : : : ; xn and later, the verifier can delegate a computation (e.g., a range search query) to the untrusted prover over the stream. The prover returns the result of the computation and a cryptographic proof for its correctness. To verify the prover's result efficiently, the verifier keeps small local (logarithmic) state, which he updates while observing the stream. The challenge is to enable the verifier to update his local state with no interaction with the prover, while ensuring the prover can compute proofs efficiently. Papamanthou et al. (EUROCRYPT 2013) introduced streaming authenticated data structures (SADS) to address the above problem. Yet their scheme is complex to describe and impractical to implement, mainly due to the use of Ajtai's lattice-based hash function. In this work we present an abstract SADS construction that can use any hash function satisfying properties that we formally define. This leads to a simpler exposition of the fundamental ideas of Papamanthou et al.'s work and to a practical implementation of a streaming authenticated data structure that employs the efficient SWIFFT hash function, which we show to comply with our abstraction. We implement both the EUROCRYPT 2013 construction and our new scheme and report major savings in prover time and public key size.

Original languageEnglish (US)
Title of host publicationCCSW 2014 - Proceedings of the 2014 ACM Cloud Computing Security Workshop, Co-located with CCS 2014
PublisherAssociation for Computing Machinery
Pages129-139
Number of pages11
EditionNovember
ISBN (Print)9781450332392
DOIs
StatePublished - Nov 7 2014
Externally publishedYes
Event6th ACM Cloud Computing Security Workshop, CCSW 2014, Held in Conjunction with the 2014 ACM Computer and Communication Security, CCS 2014 - Scottsdale, United States
Duration: Nov 7 2014 → …

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
NumberNovember
Volume2014-November
ISSN (Print)1543-7221

Conference

Conference6th ACM Cloud Computing Security Workshop, CCSW 2014, Held in Conjunction with the 2014 ACM Computer and Communication Security, CCS 2014
Country/TerritoryUnited States
CityScottsdale
Period11/7/14 → …

Keywords

  • Abstract SADS
  • GCK hash function
  • Streaming authenticated data structures

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Streaming authenticated data structures: Abstraction and implementation'. Together they form a unique fingerprint.

Cite this