Setup-Free Secure Search on Encrypted Data: Faster and Post-Processing Free
Authors: Adi Akavia (University of Haifa), Craig Gentry (IBM Research), Shai Halevi (IBM Research), Max Leibovich (University of Haifa)
Volume: 2019
Issue: 3
Pages: 87–107
DOI: https://doi.org/10.2478/popets-2019-0038
Abstract: We present a novel secure search protocol on data and queries encrypted with Fully Homomorphic Encryption (FHE). Our protocol enables organizations (client) to (1) securely upload an unsorted data array x = (x[1], . . . , x[n]) to an untrusted honest-butcurious sever, where data may be uploaded over time and from multiple data-sources; and (2) securely issue repeated search queries q for retrieving the first element (i∗ , x[i∗ ]) satisfying an agreed matching criterion i∗ = min { i ∈ [n] | IsMatch(x[i], q) = 1}, 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: – Post-processing free 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 postprocess, 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. – Faster protocol: (a) Client time and communication bandwidth are improved by a log2 n/ log log n factor. (b) Server evaluates a polynomial of degree linear in log n (compare to cubic in AFS), and overall number of multiplications improved by up to log n factor. (c) Employing only GF(2) computations (compare to GF(p) for p 2 in AFS) to gain both further speedup and compatibility to all current FHE candidates. – Order of magnitude speedup exhibited by extensive benchmarks we executed on identical hardware for implementations of ours versus AFS’s protocols. Additionally, like other FHE based solutions, our solution is setup-free: to outsource elements from the client to the server, no additional actions are performed on x except for encrypting it element by element (each element bit by bit) and uploading the resulted ciphertexts to the server.
Keywords: Secure search, Fully homomorphic encryption, Randomized algorithms, Universal hash functions
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
