Adi Akavia: Secure search in the cloud: homomorphic encryption meets coresets

Abstract

 

Secure Search is the problem of retrieving from a database table (or any unsorted array) the records matching specified attributes, as in SQL SELECT queries, but where the database and the query are encrypted. Secure search has been the leading example for practical applications of Fully Homomorphic Encryption (FHE) already in Gentry's seminal work in 2009; however, to the best of our knowledge all state-of-the-art secure search algorithms to date are realized by a polynomial of degree $\Omega(m)$ for $m$ the number of records, which is typically too slow in practice even for moderate size $m$.

 

In this work we present the first algorithm for secure search that is realized by a polynomial of degree polynomial in $\log m$. We implemented our algorithm in an open source library based on HELib implementation for the BGV's FHE scheme, and ran experiments on Amazon's EC2 cloud. Our experiments show that we can retrieve the first match in a database of millions of entries in less than an hour; moreover, for a bounded number of matches (e.g., up to 40 matches) we can retrieve all matches in a rate of billions of entries per machine per minute.

 

We achieve our results via a novel paradigm that forges a link between cryptography and modern data reduction techniques known as coresets and sketches that turn very large databases into very small ones. The key idea is that even if we don't know how to efficiently answer a query securely on the cloud, it may suffice to compute only its corresponding coreset. Since the coreset is small, the client can quickly decode the desired answer after decrypting the coreset. As a central tool we design a novel sketch that returns the first strictly-positive entry in a (not necessarily sparse) array of non-negative reals; this sketch may be of independent interest.