Outsourcing multi-version key-value stores with verifiable data freshness

Yuzhe Tang, Ling Liu, Ting Wang, Xin Hu, Reiner Sailer, Peter Pietzuch

Research output: Chapter in Book/Entry/PoemConference contribution

14 Scopus citations


In the age of big data, key-value data updated by intensive write streams is increasingly common, e.g., in social event streams. To serve such data in a cost-effective manner, a popular new paradigm is to outsource it to the cloud and store it in a scalable key-value store while serving a large user base. Due to the limited trust in third-party cloud infrastructures, data owners have to sign the data stream so that the data users can verify the authenticity of query results from the cloud. In this paper, we address the problem of verifiable freshness for multi-version key-value data. We propose a memory-resident digest structure that utilizes limited memory effectively and can have efficient verification performance. The proposed structure is named IncBM-Tree because it can INCrementally build a Bloom filter-embedded Merkle Tree. We have demonstrated the superior performance of verification under small memory footprints for signing, which is typical in an outsourcing scenario where data owners and users have limited resources.

Original languageEnglish (US)
Title of host publication2014 IEEE 30th International Conference on Data Engineering, ICDE 2014
PublisherIEEE Computer Society
Number of pages4
ISBN (Print)9781479925544
StatePublished - 2014
Externally publishedYes
Event30th IEEE International Conference on Data Engineering, ICDE 2014 - Chicago, IL, United States
Duration: Mar 31 2014Apr 4 2014

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Other30th IEEE International Conference on Data Engineering, ICDE 2014
Country/TerritoryUnited States
CityChicago, IL

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Outsourcing multi-version key-value stores with verifiable data freshness'. Together they form a unique fingerprint.

Cite this