Welcome to the resource topic for 2024/2012
Title:
GraSS: Graph-based Similarity Search on Encrypted Query
Authors: Duhyeong Kim, Yujin Nam, Wen Wang, Huijing Gong, Ishwar Bhati, Rosario Cammarota, Tajana S. Rosing, Mariano Tepper, Theodore L. Willke
Abstract:Similarity search, i.e., retrieving vectors in a database that are similar to a query, is the backbone of many applications. Especially, graph-based methods show state-of-the-art performance. For sensitive applications, it is critical to ensure the privacy of the query and the dataset.
In this work, we introduce GraSS, a secure protocol between client (query owner) and server (dataset owner) for graph-based similarity search based on fully homomorphic encryption (FHE). Both the client-input privacy against the server and the server-input privacy against the client are achievable based on underlying security assumptions on FHE.
We first propose an FHE-friendly graph structure with a novel index encoding method that makes our protocol highly scalable in terms of data size, reducing the computational complexity of neighborhood retrieval process from O(n^2) to \tilde{O}(n) for the total number of nodes n. We also propose several core FHE algorithms to perform graph operations under the new graph structure. Finally, we introduce GraSS, an end-to-end solution of secure graph-based similarity search based on FHE. To the best of our knowledge, it is the first FHE-based solution for secure graph-based database search.
We implemented GraSS with an open-source FHE library and estimated the performance on a million-scale dataset. GraSS identifies (approximate) top-16 in about 83 hours achieving search accuracy of 0.918, making it over 28\times faster than the previous best-known FHE-based solution.
ePrint: https://eprint.iacr.org/2024/2012
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 .