A Privacy-Preserving Index for Range Queries
Database outsourcing is an emerging data management paradigm which has the potential to transform the IT operations of corporations. In this paper the authors address privacy threats in database outsourcing scenarios where trust in the service provider is limited. Specifically, they analyze the data partitioning (bucketization) technique and algorithmically develop this technique to build privacy-preserving indices on sensitive attributes of a relational table. Such indices enable an untrusted server to evaluate obfuscated range queries with minimal information leakage. They analyze the worst-case scenario of inference attacks that can potentially lead to breach of privacy (e.g., estimating the value of a data element within a small error margin) and identify statistical measures of data privacy in the context of these attacks.