Paper 2024/2012
GraSS: Graph-based Similarity Search on Encrypted Query
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
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- Fully homomorphic encryptionsimilarity searchgraph-based methodprotocol
- Contact author(s)
-
duhyeong kim @ intel com
yujinnam @ ucsd edu
wen wang @ intel com
huijing gong @ intel com
ishwar s bhati @ intel com
rosario cammarota @ intel com
tajana @ ucsd edu
marianotepper @ gmail com
ted willke @ intel com - History
- 2024-12-13: approved
- 2024-12-13: received
- See all versions
- Short URL
- https://ia.cr/2024/2012
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/2012, author = {Duhyeong Kim and Yujin Nam and Wen Wang and Huijing Gong and Ishwar Bhati and Rosario Cammarota and Tajana S. Rosing and Mariano Tepper and Theodore L. Willke}, title = {{GraSS}: Graph-based Similarity Search on Encrypted Query}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/2012}, year = {2024}, url = {https://eprint.iacr.org/2024/2012} }