Pacmann: Efficient Private Approximate Nearest Neighbor Search

Thank you for your comments!

Privacy Definition: We will make our privacy definition clear in the next version. Specifically, we achieve cryptographically strong privacy assuming the adversary acting as the database owner is malicious, inheriting the privacy guarantee of the Piano PIR scheme: the adversary can choose the underlying database maliciously and respond to the client arbitrarily. It records all interactions with the client and tries to infer non-trivial information about the client’s queries. We prove that such an adversary learns negligible information about the queries. We do require an honest database owner for the utility guarantee – after all a malicious database owner can just refuse the service and respond randomly.

More formally, we proved the adversary’s views in the following two experiments are computationally indistinguishable:

Real: 
	The adversary chooses the underlying database. An honest client interacts with the adversary who acts as the server. In each time step, the adversary can adaptively choose a query vector based on its previous view, and the client will invoke the query algorithm with the chosen query vector as input. The adversary records the transcript of the interaction. 

Ideal: 
	The adversary chooses the underlying database. A simulator simulates the client and interacts with the adversary who acts as the server. In each time step, the adversary can adaptively choose a query vector based on its previous view, and the simulator is invoked without the input query vectors. The adversary records the transcript of the interaction. 

DP-guarantee: A notable existing DP-based work is Wally[1], which implements the same cluster-based search functionality as Tiptoe. We achieved >90% recall@10 in the SIFT dataset, a significant improvement over the 35% recall@10 achieved by the cluster-based method used by Wally. Moreover, Wally needs additional waiting to batch many clients’ queries, since they offer a batched scheme. We will add this comparison in the final version.

In terms of achieving DP-type privacy guarantee, replacing the underlying PIR in our scheme with DP-based PIR works, e.g., [2], could lead to further performance improvements. We leave this as an interesting future direction.

[1]: Asi, Hilal, et al. "Scalable Private Search with Wally." arXiv preprint arXiv:2406.06761 (2024).

[2]: Albab, Kinan Dak, et al. "Batched differentially private information retrieval." 31st USENIX Security Symposium USENIX Security, 2022.

Thank you for your comments!

Q1: We will make our security analysis clear in the next version. Specifically, we achieve cryptographically strong privacy assuming the adversary acting as the database owner is malicious, inheriting the security guarantee of the Piano PIR scheme: the adversary can choose the underlying database maliciously and respond to the client arbitrarily. It records all interactions with the client and tries to infer non-trivial information about the client’s queries. We prove that such an adversary learns negligible information about the queries. We do require an honest database owner for the utility guarantee – after all a malicious database owner can just refuse the service and respond randomly.

Q2: Our current evaluation gave an unfair advantage to the Tiptoe-based solution by simulating its homomorphic encryption operations with simple plaintext operations. We still achieved performance gain in this case. To verify the validity of our simulation, we checked against the evaluation result in the original Tiptoe paper and our simulation was ~10% faster in online latency than their reported numbers. We document this comparison in Appendix D.2. We could not run the original Tiptoe implementation because it requires computationally intensive preprocessing, requiring dozens of GPU servers running hundreds of core-hours as documented in their paper. Our experiments are run on a single server-grade machine.

Thank you for your comments!

Practical Applications: Many practical scenarios that require privacy-preserving semantic information matching/searching could benefit from our solution, where the database sizes range from millions to billions. Here are some realistic examples:

1. Privacy-preserving harmful content detection. For example, a security software can utilize our solution to semantically match a suspicious file from a user against a list of potential viruses or harmful contents without compromising the user’s privacy. An example is [1] .
2. Privacy-preserving biometric information searching: we can perform fuzzy matching for the users’ sensitive biometric information against a public database for identification or information discovery. An example is [2].

[1] https://www.apple.com/child-safety/pdf/CSAM_Detection_Technical_Summary.pdf

[2] Hong, Matthew M., et al. "Secure Discovery of Genetic Relatives across Large-Scale and Distributed Genomic Datasets." International Conference on Research in Computational Molecular Biology. 2024.

Improvements over the previous work:

1. We achieve the latency reduction and also a significant quality improvement simultaneously – improving from 35% recall@10 to 91% recall@10. If we aim for the same 35% recall, the latency reduction will be around 8-13x under different network conditions, as shown in Figure 2(b).

2. Our 1.3 - 2.2x latency reduction is w.r.t a plaintext linear scan that lower bounds the latency of the prior work, Tiptoe. Tiptoe needs a linear scan not in plaintext but in homomorphic evaluations. Even though they performed offline work to save online time, they still need quantization (full precision to 4-bit) to get reasonable online latency —- this is one source of their significant utility loss.

3. Even with strong utility improvement, our scheme is asymptotically better in computation than existing methods as we take a sublinear amortized cost per query, while the previous schemes require linear cost per query.

We will also incorporate the editorial comments in the next version.

Thank you for your comments!

Asymptotic Cost: The $O(n)$ computation and communication are paid only once upfront during preprocessing and afterward every query takes only $O(CH\sqrt{n})$ computation and communication, where $C$ is the degree of the graph and $H$ is the maximum hop numbers for each query. The existing schemes such as Tiptoe[3] and Preco[4] pay $O(n)$ computation for every query. The $O(n)$ preprocessing computation is inevitable, implied by lower bounds for PIR (see [1][2]). Our scheme achieves $O(CH\sqrt{n})$ amortized communication, and the $\sqrt{n}$ part is necessary subject to using only symmetric key primitive and $\sqrt{n}$ client space, due to known lower bounds [5]. We can also implement our scheme with two non-colluding servers by having another server prepare the hints for the client during the preprocessing so that the preprocessing communication will be improved from $O(n)$ to $O(\sqrt n)$.

Practical Applications: We are not expecting to scale our solution to a Google-search-size database, but many practical scenarios that require privacy-preserving semantic information matching/searching could still benefit from our solution, where the database sizes range from millions to billions. Here are some realistic examples:

1. Privacy-preserving harmful content detection. For example, a security software can utilize our solution to semantically match a suspicious file from a user against a list of potential viruses or harmful contents without compromising the user’s privacy [6].
2. Privacy-preserving biometric information searching: we can perform fuzzy matching for the users’ sensitive biometric information against a public database for identification or information discovery. See an existing example [7].

[1] Beimel, Amos, Yuval Ishai, and Tal Malkin. "Reducing the servers computation in private information retrieval: PIR with preprocessing." Crypto, 2000.

[2] Yeo, Kevin. "Lower bounds for (batch) PIR with private preprocessing." Eurocrypt, 2023.

[3] Henzinger, Alexandra, et al. "Private web search with Tiptoe." SOSP, 2023.

[4] Servan-Schreiber, Sacha, Simon Langowski, and Srinivas Devadas. "Private approximate nearest neighbor search with sublinear communication." IEEE S&P, 2022.

[5] Ishai, Yuval, Elaine Shi, and Daniel Wichs. "PIR with Client-Side Preprocessing: Information-Theoretic Constructions and Lower Bounds." Crypto, 2024.

[6] https://www.apple.com/child-safety/pdf/CSAM_Detection_Technical_Summary.pdf

[7] Hong, Matthew M., et al. "Secure Discovery of Genetic Relatives across Large-Scale and Distributed Genomic Datasets." International Conference on Research in Computational Molecular Biology. 2024.