Efficient and secure exact-match queries in outsourced databases

• Published in: World wide web (Bussum) 2015-05, Vol.18 (3), p.567-605
• Main Authors: Heidinger, Clemens, Böhm, Klemens, Buchmann, Erik, Spoo, Martin
• Format: Article
• Language: English
• Subjects: Computer Science; Database Management; Information Systems Applications (incl.Internet); Operating Systems
• ISSN: 1386-145X; 1573-1413
• DOI: 10.1007/s11280-013-0270-0

Data management can now be outsourced to cloud service providers like Amazon Web Services or IBM SmartCloud. This calls for encrypted data-representation schemes that also give way to efficient query processing. State-of-the-art approaches are overly expensive for exact-match queries in the worst case, or they do not ensure privacy if an adversary knows the data distribution. In this paper, we propose a new privacy approach without these shortcomings. It makes use of encryption, obfuscated indices, and data fragmentation. To speed up query processing, we propose three novel data-transformation and query-execution schemes. For two schemes, we prove that an adversary capable of solving any polynomial problem cannot determine if any attribute values appear together in a tuple. Thus, with our schemes, sensitive data is not linked to personally identifiable information. To evaluate our third scheme, we propose a measure that quantifies the risk of disclosure. We evaluate our approach on real-world folksonomy data. Our evaluation shows that its average response time of exact-match queries with 15 million tuples is under one second on a conventional desktop PC.