Setup-Free Secure Search on Encrypted Data: Faster and Post-Processing Free
Adi Akavia, Craig Gentry, Shai Halevi, and Max Leibovich
Abstract
We present a novel protocol on data and queries encrypted with Fully Homomorphic Encryption (FHE).
Our protocol enables organizations (client) to (1) securely upload an unsorted data array to an untrusted honest-but-curious sever, where data may be uploaded over time and from multiple data-sources; and (2) securely issue repeated search queries for retrieving the first element satisfying an agreed matching criterion , as well as fetching the next matching elements with further interaction.
For security, the client encrypts the data and queries with FHE prior to uploading, and the server processes the ciphertexts to produce the result ciphertext for the client to decrypt.
Our secure search protocol improves over the prior state-of-the-art for secure search on FHE encrypted data (Akavia, Feldman, Shaul (AFS), CCS'2018) in achieving:
(1) protocol where the server produces a ciphertext for the correct search outcome with overwhelming success probability.This is in contrast to returning a list of candidates for the client to post-process, or suffering from a noticeable error probability, in AFS. Our post-processing freeness enables the server to use secure search as a sub-component in a larger computation without interaction with the client.
(2) (a) Client time and communication bandwidth are improved by a factor. (b) Server evaluates a polynomial of degree linear in (compare to cubic in AFS), and overall number of multiplications improved by up to factor.(c) Employing only computations (compare to for in AFS) to gain both further speedup and compatibility to all current FHE candidates.
(3) we executed on identical hardware for implementations of ours versus AFS's protocols.
Additionally, like other FHE based solutions, out solution is setup-free: to outsource elements from the client to the server, no additional actions are performed on except for encrypting it element by element (each element bit by bit) and uploading the resulted ciphertexts to the server.
@misc{cryptoeprint:2018/1235,
author = {Adi Akavia and Craig Gentry and Shai Halevi and Max Leibovich},
title = {Setup-Free Secure Search on Encrypted Data: Faster and Post-Processing Free},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/1235},
year = {2018},
url = {https://eprint.iacr.org/2018/1235}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.