Cryptology ePrint Archive: Report 2016/1063

Log-Structured Authenticated Data Structures for Secure Cloud Storage with Minimal Trust

Yuzhe (Richard) Tang and Ju Chen and Kai Li

Abstract: In the age of cloud, it is pressing to support an authenticated data storage service (e.g., trustworthy Dropbox) for write-intensive big-data workloads. While existing authenticated data structure protocols protect the data authenticity, most of them are designed based on update-in-place data structures, causing high overhead in write-intensive workloads.

In this work, we propose LPAD, an authenticated data structure designed uniquely on the log-structured merge tree (LSM tree). The LPAD supports streaming, non-interactive data updates from cloud clients. To support the efficient verifiable merge of an LSM tree, we propose to build a system of the LPAD on Intel SGX where the merge operation necessarily runs inside the SGX enclave. The rest of the LSM store runs outside the enclave, and by this means, the system features a minimal trusted computing base (TCB). We also propose the design and implementation of a high-performance LPAD digest structure of where the digests and data are co-located on disk.

We conduct an extensive performance study of our LPAD prototype. With YCSB workloads, we show that the LPAD achieves the performance improvement by an order of magnitude in serving write-intensive workloads.

Category / Keywords: applications / SGX, TEE, hash functions, authentication codes

Date: received 13 Nov 2016, last revised 16 May 2019

Contact author: ytang100 at syr edu

Available format(s): PDF | BibTeX Citation

Version: 20190516:152205 (All versions of this report)

Short URL: ia.cr/2016/1063


[ Cryptology ePrint archive ]