Lightweight authentication of freshness in outsourced key-value stores

Yuzhe Tang, Ting Wang, Ling Liu, Xin Hu, Jiyong Jang

Research output: Contribution to conferencePaperpeer-review

14 Scopus citations


Data outsourcing offers cost-effective computing power to manage massive data streams and reliable access to data. Data owners can forward their data to clouds, and the clouds provide data mirroring, backup, and online access services to end users. However, outsourcing data to untrusted clouds requires data authenticity and query integrity to remain in the control of the data owners and users. In this paper, we address the authenticated data-outsourcing problem specifically for multi-version key-value data that is subject to continuous updates under the constraints of data integrity, data authenticity, and "freshness" (i.e., ensuring that the value returned for a key is the latest version). We detail this problem and propose INCBM-TREE, a novel construct delivering freshness and authenticity. Compared to existing work, we provide a solution that offers (i) lightweight signing and verification on massive data update streams for data owners and users (e.g., allowing for small memory footprint and CPU usage for a low-budget IT department), (ii) immediate authentication of data freshness, (iii) support of authentication in the presence of both real-time and historical data accesses. Extensive benchmark evaluations demonstrate that INCBM-TREE achieves higher throughput (in an order of magnitude) for data stream authentication than existing work. For data owners and end users that have limited computing power, INCBM-TREE can be a practical solution to authenticate the freshness of outsourced data while reaping the benefits of broadly available cloud services.

Original languageEnglish (US)
Number of pages10
StatePublished - Dec 8 2014
Event30th Annual Computer Security Applications Conference, ACSAC 2014 - New Orleans, United States
Duration: Dec 8 2014Dec 12 2014


Other30th Annual Computer Security Applications Conference, ACSAC 2014
Country/TerritoryUnited States
CityNew Orleans

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'Lightweight authentication of freshness in outsourced key-value stores'. Together they form a unique fingerprint.

Cite this