Randex: Mitigating Range Injection Attacks on Searchable Encryption

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.