Friday, September 15, 2017 - 10:30am to 12:00pm

Location:

Hewlett G882

Speaker:

Adi Akavia, The Academic College of Tel-Aviv Yaffo

Seminar group:

Abstract

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.