BLUE

ePrint Updates

@eprint.bsky.social

Unofficial bot tracking updates to the IACR Cryptology ePrint Archive (eprint.iacr.org/). Maintained by @str4d.xyz. Currently only posts about new papers. Author names are linkified to Bluesky accounts; contact maintainer for inclusion or removal.

407 followers1 following2.9k posts

EUeprint.bsky.socialOct 9, 2024 11:10am

Pacmann: Efficient Private Approximate Nearest Neighbor Search (Mingxun Zhou, Elaine Shi, Giulia Fanti) ia.cr/2024/1600

Abstract. We propose a new private Approximate Nearest Neighbor (ANN) search scheme named Pacmann that allows a client to perform ANN search in a vector database without revealing the query vector to the server. Unlike prior constructions that run encrypted search on the server side, Pacmann carefully offloads limited computation and storage to the client, no longer requiring computationally-intensive cryptographic techniques. Specifically, clients run a graph-based ANN search, where in each hop on the graph, the client privately retrieves local graph information from the server. To make this efficient, we combine two ideas: (1) we adapt a leading graph-based ANN search algorithm to be compatible with private information retrieval (PIR) for subgraph retrieval; (2) we use a recent class of PIR schemes that trade offline preprocessing for online computational efficiency. Pacmann achieves significantly better search quality than the state-of-the-art private ANN search schemes, showing up to 2.5× better search accuracy on real-world datasets than prior work and reaching 90% quality of a state-of-the-art non-private ANN algorithm. Moreover on large datasets with up to 100 million vectors, Pacmann shows better scalability than prior private ANN schemes with up to 2.6× reduction in computation time and 1.3× reduction in overall latency.

ePrint Updates

@eprint.bsky.social

407 followers1 following2.9k posts