CS2: A Searchable Cryptographic Cloud Storage System

Cloud storage provides a highly available, easily accessible and inexpensive remote data repository to clients who cannot afford to maintain their own storage infrastructure. While many applications of cloud storage require security guarantees against the cloud provider (e.g., storage of high-impact business data or medical records), most services cannot guarantee that the provider will not see or modify client data. This is largely because the current approaches for providing security (e.g., encryption and digital signatures) diminish the utility and/or performance of cloud storage.

This paper presents CS2, a cryptographic cloud storage system that guarantees confidentiality, integrity and verifiability without sacrificing utility. In particular, while CS2 provides security against the cloud provider, clients are still able not only to efficiently access their data through a search interface but also to add and delete files securely.

The CS2 system is based on new highly-efficient and provably-secure cryptographic primitives and protocols. In particular, we (1) construct the first searchable symmetric encryption scheme that is adaptively secure, dynamic and achieves sub-linear search time; (2) introduce and construct search authenticators (which allow a client to efficiently verify the correctness of search operations); and (3) design an efficient and dynamic proof of data possession scheme. Based in part on our new constructions, we propose two cryptographic protocols for cloud storage which we prove secure in the ideal/real-world paradigm. The first protocol implements standard keyword search. Our second protocol implements what we refer to as assisted keyword search, where a user performs a keyword search, sees a summary of the results and asks for a subset of these results.

Experimental results from an implementation of CS2 over both simulated and real-world data sets demonstrate that all operations achieve practical performance.