GIT-CERCS-14-03
Yuzhe Tang, Ting Wang, Xin Hu, Jiyong Jang, Ling Liu, Peter Pietzuch,
Authentication of Freshness for Outsourced Multi-Version Key-Value Stores
Data outsourcing offers cost-effective computing
power to manage massive data streams and reliable access
to data. For example, 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 authentication and query
integrity to remain in the control of the data owners and users.
In this paper, we address this 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 on mobile user
devices), (ii) integrity of both real-time and historic data, and
(iii) support for both real-time and periodic data publication.
Extensive benchmark evaluations demonstrate that INCBM-
TREE achieves more 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.