EncKV: an encrypted key-value store with rich queries

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

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

35 Citations (Scopus)


Distributed data stores have been rapidly evolving to serve the needs of large-scale applications such as online gaming and real-time targeting. In particular, distributed key-value stores have been widely adopted due to their superior performance. However, these systems do not guarantee to provide strong protection of data confientiality, and as a result fall short of addressing serious privacy concerns raised from massive data breaches. In this paper, we introduce EncKV, an encrypted keyvalue store with secure rich query support. First, EncKV stores encrypted data records with multiple secondary attributes in the form of encrypted key-value pairs. Second, it leverages the latest practical primitives for searching over encrypted data, i.e., searchable symmetric encryption and order-revealing encryption, and provides encrypted indexes with guaranteed security to support exact-match and rangematch queries via secondary attributes of data records. Third, it carefully integrates these indexes into a distributed index framework to facilitate secure query processing in parallel. To mitigate recent inference attacks on encrypted database systems, EncKV protects the order information during range queries, and presents an interactive batch query mechanism to further hide the associations across data values on different attributes. We implement an EncKV prototype on a Redis cluster, and conduct an extensive set of performance evaluations on the Amazon EC2 public cloud platform. Our results show that EncKV effectively preserves the efficiency and scalability of plaintext distributed key-value stores.

Original languageEnglish
Title of host publicationASIA CCS' 2017 - Proceedings of the 2017 ACM Asia Conference on Computer and Communications Security
EditorsAhmad-Reza Sadegh, Xun Yi
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages13
ISBN (Print)9781450349444
Publication statusPublished - 2 Apr 2017
Externally publishedYes
EventACM Symposium on Information, Computer and Communications Security 2017 - Abu Dhabi, United Arab Emirates
Duration: 2 Apr 20176 Apr 2017
Conference number: 12th


ConferenceACM Symposium on Information, Computer and Communications Security 2017
Abbreviated titleAsiaCCS 2017
Country/TerritoryUnited Arab Emirates
CityAbu Dhabi
Internet address


  • Encrypted key-value store
  • Orderrevealing encryption
  • Searchable encryption

Cite this