Enabling encrypted rich queries in distributed key-value stores

Yu Guo, Xingliang Yuan, Xinyu Wang, Cong Wang, Baochun Li, Xiaohua Jia

Research output: Contribution to journalArticleResearchpeer-review

30 Citations (Scopus)


To accommodate massive digital data, distributed data stores have become the main solution for cloud services. Among others, key-value stores are widely adopted due to their superior performance. But with the rapid growth of cloud storage, there are growing concerns about data privacy. In this paper, we design and build EncKV, an encrypted and distributed key-value store with rich query support. First, EncKV partitions data records with secondary attributes into a set of encrypted key-value pairs to hide relations between data values. Second, EncKV uses the latest cryptographic techniques for searching on encrypted data, i.e., searchable symmetric encryption (SSE) and order-revealing encryption (ORE) to support secure exact-match and range-match queries, respectively. It further employs a framework for encrypted and distributed indexes supporting query processing in parallel. To address inference attacks on ORE, EncKV is equipped with an enhanced ORE scheme with reduced leakage. For practical considerations, EncKV also enables secure system scaling in a minimally intrusive way. We complete the prototype implementation and deploy it on Amazon Cloud. Experimental results confirm that EncKV preserves the efficiency and scalability of distributed key-value stores.

Original languageEnglish
Pages (from-to)1283-1297
Number of pages15
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number6
Publication statusPublished - Jun 2019


  • Encrypted Key-value Store
  • Order-revealing Encryption
  • Searchable Encryption

Cite this