Randex: Mitigating Range Injection Attacks on Searchable Encryption

Hanyu Quan, Hao Liu, Boyang Wang, Ming Li, Yuqing Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


Searchable Encryption enables search functions over encrypted data on an untrusted server without the need of accessing data or queries in plaintext. To boost search time, most of the Searchable Encryption schemes leak access pattern. Unfortunately, by harnessing access pattern, a variation of a chosen-query attack, named range injection attack, can efficiently recover sensitive data in any encrypted tuple. The privacy leakage under a range injection attack is severe, and it is imperative to strengthen the privacy of searchable encrypted data. In this paper, we devise an efficient mechanism, referred to as Randex, to mitigate leakage on searchable encrypted data. Specifically, we apply pre-encryption obfuscation by deploying Randomized Response, which obfuscates access pattern. Randex renders minimal tradeoffs to the correctness of range queries, and is compatible with any Searchable Encryption scheme. We formally prove that Randex achieves-local differential privacy and rigorously analyze an adversary's guessing probability against range injection attacks. We implement Randex and conduct extensive experiments on a synthetic dataset with 1 million tuples and a real-world dataset with 299 thousand tuples. Our results suggest that, with only 4% false negatives and no false positives, Randex can suppress an adversary's guessing probability to 0.17, which is significantly lower than the guessing probability of 1 without the privacy protection offered by Randex.

Original languageEnglish (US)
Title of host publication2019 IEEE Conference on Communications and Network Security, CNS 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages9
ISBN (Electronic)9781538671177
StatePublished - Jun 2019
Event2019 IEEE Conference on Communications and Network Security, CNS 2019 - Washington, United States
Duration: Jun 10 2019Jun 12 2019

Publication series

Name2019 IEEE Conference on Communications and Network Security, CNS 2019


Conference2019 IEEE Conference on Communications and Network Security, CNS 2019
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Information Systems and Management
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'Randex: Mitigating Range Injection Attacks on Searchable Encryption'. Together they form a unique fingerprint.

Cite this