Strengthening Order Preserving Encryption with Differential Privacy

Ciphertexts of an order-preserving encryption (OPE) scheme preserve the order of their corresponding plaintexts. However, OPEs are vulnerable to inference attacks that exploit this preserved order. Differential privacy (DP) has become the de-facto standard for data privacy. One of the most attractive properties of DP is that any post-processing computation, such as inference attacks, performed on the noisy output of a DP algorithm does not degrade its privacy guarantee. In this work, we propose a novel differentially private order preserving encryption scheme, OP ε. Under OP ε, the leakage of order from the ciphertexts is differentially private. Consequently, in the least, OP ε ensures a formal guarantee (a relaxed DP guarantee) even in the face of inference attacks. To the best of our knowledge, this is the first work to combine DP with a OPE. OP ε is based on a novel differentially private order preserving encoding scheme, OPεc, that can be of independent interest in the local DP setting. We demonstrate OP ε's utility in answering range queries via empirical evaluation on four real-world datasets. For instance, OP ε misses only around 4 in every 10K correct records on average for a dataset of size 732K with an attribute of domain size 18K and ε= 1.