Welcome to the resource topic for 2018/1235
Title:
Setup-Free Secure Search on Encrypted Data: Faster and Post-Processing Free
Authors: Adi Akavia, Craig Gentry, Shai Halevi, Max Leibovich
Abstract:We present a novel \textit{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],\ldots,x[n]) 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 q for retrieving the first element (i^*,x[i^*]) satisfying an agreed matching criterion i^* = \min\ \left\{ \left.i\in[n] \;\right\vert \mathsf{IsMatch}(x[i],q)=1 \right\}, 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) \textit{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 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) \textit{Faster protocol:}(a) Client time and communication bandwidth are improved by a \log^2n/\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 \textrm{GF}(2) computations (compare to \textrm{GF}(p) for p \gg 2 in AFS) to gain both further speedup and compatibility to all current FHE candidates. (3) \textit{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, out 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.
ePrint: https://eprint.iacr.org/2018/1235
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .