Paper 2024/1774
PANTHER: Private Approximate Nearest Neighbor Search in the Single Server Setting
Abstract
Approximate nearest neighbor search (ANNS), also known as vector search, is an important building block for varies applications, such as databases, biometrics, and machine learning. In this work, we are interested in the private ANNS problem, where the client wants to learn (and can only learn) the ANNS results without revealing the query to the server. Previous private ANNS works either suffers from high communication cost (Chen et al., USENIX Security 2020) or works under a weaker security assumption of two non-colluding servers (Servan-Schreiber et al., SP 2022). We present Panther, an efficient private ANNS framework under the single server setting. Panther achieves its high performance via several novel co-designs of private information retrieval (PIR), secretsharing, garbled circuits, and homomorphic encryption. We made extensive experiments using Panther on four public datasets, results show that Panther could answer an ANNS query on 10 million points in 23 seconds with 318 MB of communication. This is more than 6× faster and 18× more compact than Chen et al..
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- Private Information RetrievalHomomorphic EncryptionMultiparty ComputationNearest Neighbor Search
- Contact author(s)
-
ljy404490 @ antgroup com
zhicong hzc @ antgroup com
zhangmin @ iscas ac cn
liujian2411 @ zju edu cn
vince hc @ antgroup com
lenx wei @ antgroup com
yuanben cwg @ antgroup com - History
- 2024-11-01: approved
- 2024-10-31: received
- See all versions
- Short URL
- https://ia.cr/2024/1774
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2024/1774,
author = {Jingyu Li and Zhicong Huang and Min Zhang and Jian Liu and Cheng Hong and Tao Wei and Wenguang Chen},
title = {{PANTHER}: Private Approximate Nearest Neighbor Search in the Single Server Setting},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1774},
year = {2024},
url = {https://eprint.iacr.org/2024/1774}
}