Building an Encrypted, Distributed, and Searchable Key-value Store

Modern distributed key-value stores are offering superior performance, incremental scalability, and fine availability for data-intensive computing and cloud-based applications. Among those distributed data stores, the designs that ensure the confidentiality of sensitive data, however, have not been fully explored yet. In this paper, we focus on designing and implementing an encrypted, distributed, and searchable key-value store. It achieves strong protection on data privacy while preserving all the above prominent features of plaintext systems. We first design a secure data partition algorithm that distributes encrypted data evenly across a cluster of nodes. Based on this algorithm, we propose a secure transformation layer that supports multiple data models in a privacy-preserving way, and implement two basic APIs for the proposed encrypted key-value store. To enable secure search queries for secondary attributes of data, we leverage searchable symmetric encryption to design the encrypted secondary indexes which consider security, efficiency, and data locality simultaneously, and further enable secure query processing in parallel. For completeness, we present formal security analysis to demonstrate the strong security strength of the proposed designs. We implement the system prototype and deploy it to a cluster at Microsoft Azure. Comprehensive performance evaluation is conducted in terms of Put/Get throughput, Put/Get latency under different workloads, system scaling cost, and secure query performance. The comparison with Redis shows that our prototype can function in a practical manner.