Efficient Index-based Search Protocols for Encrypted Databases

Abstract

It is astonishing to see more and more services built on user-oriented data, providing numerous tools to improve ones daily life. Nowadays, data collected from numerous sources is being used to monitor daily activities, i.e., monitoring patients. These innovations allow for more cost-efficient and scalable solutions. Nevertheless, these types of services can pose a threat to the privacy of individuals due to the possibility of leaking highly privacy-sensitive data. Therefore, it is essential to design such systems in a privacy-preserving manner. Inspired by a real-life project in the health-care domain, we propose to secure the data using encryption, while enabling the involved parties to run queries directly on this encrypted data. A vital component of such a system is searching for specific data entries within a large dataset. In this work, we present two cryptographic protocols that complete such a query by creating an encrypted vector in a simulation secure way. These vectors cons ist of a 1 for intended database entry, whereas other items would be represented as a 0. By creating index tables before the execution of the queries, it has become possible to execute a search query with high performance. As we show in our analyses, it takes less than one second to find the matching encrypted data-entry within a database with 100K records. Our proposal is generic, can be applied to several application domains, and practically compared to similar works.