Secure Search on the Cloud via Coresets and Sketches
This work addresses the efficiency bottleneck in secure search for encrypted databases, offering a practical solution for cloud-based applications, though it is incremental in applying existing data summarization techniques to homomorphic encryption.
The paper tackled the problem of secure search on encrypted databases, which previously required high-degree polynomials and was too slow for practical use, by introducing an algorithm using coresets and sketches that reduces the polynomial degree to logarithmic in the number of records, enabling retrieval of the first match in a database of millions of entries in less than an hour on a single machine.
\emph{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) starting in Gentry's seminal work; however, to the best of our knowledge all state-of-the-art secure search algorithms to date are realized by a polynomial of degree $Ω(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 Brakerski-Gentry-Vaikuntanthan'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 using a single machine; the time reduced almost linearly with the number of machines. Our result utilizes a new paradigm of employing coresets and sketches, which are modern data summarization techniques common in computational geometry and machine learning, for efficiency enhancement for homomorphic encryption. As a central tool we design a novel sketch that returns the first positive entry in a (not necessarily sparse) array; this sketch may be of independent interest.