Building an encrypted, distributed, and searchable key-value store

Xingliang Yuan, Xinyu Wang, Cong Wang, Chen Qian, Jianxiong Lin

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

13 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationASIA CCS 2016 - Proceedings of the 11th ACM Asia Conference on Computer and Communications Security
Subtitle of host publicationMay 30 – June 3, 2016, Xi’an, China
EditorsXiaoFeng Wang, Xinyi Huang
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages12
ISBN (Electronic)9781450342339
Publication statusPublished - 2016
Externally publishedYes
EventACM Symposium on Information, Computer and Communications Security 2016 - Xi'an, China
Duration: 30 May 20163 Jun 2016
Conference number: 11th


ConferenceACM Symposium on Information, Computer and Communications Security 2016
Abbreviated titleAsiaCCS 2016
Internet address


  • Key-value Store
  • Searchable Encryption

Cite this