Paper 2018/245

Secure Search via Multi-Ring Fully Homomorphic Encryption

Adi Akavia, Dan Feldman, and Hayim Shaul

Abstract

Secure search is the problem of securely retrieving from a database table (or any unsorted array) the records matching specified attributes, as in SQL ``SELECT...WHERE...'' 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) since Gentry's seminal work in 2009, attaining the desired properties of a single-round low-communication protocol with semantic security for database and query (even during search). Nevertheless, the wide belief was that the high computational overhead of current FHE candidates is too prohibitive in practice for secure search solutions (except for the restricted case of searching for a uniquely identified record as in SQL UNIQUE constrain and Private Information Retrieval). This is due to the high degree in existing solutions that is proportional at least to the number of database records m. We present the first algorithm for secure search that is realized by a polynomial of logarithmic degree (log m)^c for a small constant c>0. We implemented our algorithm in an open source library based on HElib, and ran experiments on Amazon's EC2 cloud with up to 100 processors. Our experiments show that we can securely search to retrieve database records in a rate of searching in millions of database records in less than an hour on a single machine. We achieve our result by: (1) Designing a novel sketch that returns the first strictly-positive entry in a (not necessarily sparse) array of non-negative real numbers; this sketch may be of independent interest. (2) Suggesting a multi-ring evaluation of FHE -- instead of a single ring as in prior works -- and leveraging this to achieve an exponential reduction in the degree.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. MAJOR revision.https://arxiv.org/abs/1708.05811
Keywords
secure searchfully homomorphic encryptionarithmetic circuitlow degreeimplementationsecure outsourcing
Contact author(s)
adi akavia @ gmail com
History
2018-03-07: received
Short URL
https://ia.cr/2018/245
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/245,
      author = {Adi Akavia and Dan Feldman and Hayim Shaul},
      title = {Secure Search via Multi-Ring Fully Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2018/245},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/245}},
      url = {https://eprint.iacr.org/2018/245}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.