Lightweight authentication of freshness in outsourced key-value stores

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

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

7 Scopus citations

Abstract

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)
Title of host publicationACM International Conference Proceeding Series
PublisherAssociation for Computing Machinery
Pages176-185
Number of pages10
Volume2014-December
EditionDecember
DOIs
StatePublished - Dec 8 2014
Event30th Annual Computer Security Applications Conference, ACSAC 2014 - New Orleans, United States
Duration: Dec 8 2014Dec 12 2014

Other

Other30th Annual Computer Security Applications Conference, ACSAC 2014
CountryUnited States
CityNew Orleans
Period12/8/1412/12/14

    Fingerprint

ASJC Scopus subject areas

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

Cite this

Tang, Y., Wang, T., Liu, L., Hu, X., & Jang, J. (2014). Lightweight authentication of freshness in outsourced key-value stores. In ACM International Conference Proceeding Series (December ed., Vol. 2014-December, pp. 176-185). Association for Computing Machinery. https://doi.org/10.1145/2664243.2664244