Paper 2018/1003

Secure Data Retrieval On The Cloud Homomorphic Encryption Meets Coresets

Adi Akavia and Dan Feldman and Hayim Shaul

Abstract

\emph{Secure Report} is the problem of retrieving from a database table (e.g. on the cloud) all records matching specified attributes, as in SQL SELECT queries, but where the query and possibly the database are encrypted. Here, only the client has the secret key, but still the server (e.g. cloud owner) can compute and return the encrypted result. Secure report is theoretically possible with Fully Homomorphic Encryption (FHE). However, the current state-of-the-art solutions are realized by a polynomial of degree that is at least linear in the number $m$ of records, which is too slow in practice even for very small databases. Nevertheless, in this work we present the first algorithm for secure report that is realized by a polynomial of degree polynomial in $\log m$, as well as the first implementation of secure (FHE) report. This is by suggesting a novel paradigm that forges a link between cryptography and modern data summarization techniques known as core-sets, and sketches in particular. The key idea is to compute only a core-set of the desired report. Since the core-set is small, the client can quickly decode the desired report that the server computes after decrypting its core-set. We implemented our main reporting system including all its sub-routines in an open source library. This is the first implemented system that can answer such database queries under the strong secure notion of FHE. As our analysis promises, the experimental results show that we can run secure report queries on billions records compared to few thousands in previous FHE papers. We hope that our results and open code would lead to the first FHE database engine in the near future.