zkANN: Efficient and Verifiable ANN Search with Enhanced Data Privacy

In recent years, graph-based indexing has emerged as a prominent technique for supporting Approximate Nearest Neighbor Search (ANNS) on massive multimedia datasets. When this data is outsourced to cloud servers, providing verifiable ANNS (vANNS) services presents new challenges. Existing methods typically store intermediate results in Verification Object (VO), enabling users to reproduce the query process and verify the authenticity of the results. However, these intermediate results inadvertently expose excessive data to users, raising privacy concerns. Furthermore, as datasets scale, the VO size grows rapidly, severely impacting efficiency. In this paper, we propose zkANN, a system that combines Merkle trees and zero-knowledge proofs (ZKP) to achieve high-performance query processing while preventing data leakage—a critical capability absent in state-of-the-art (SOTA) methods. Specifically, we employ zk-SNARKs to generate proofs for essential steps in VO construction, eliminating the exposure of raw data. We further propose a monotonicity-aware VO compression technique to enhance efficiency. Experimental results demonstrate that while zkANN incurs additional overhead to ensure data confidentiality, it still outperforms SOTA methods. Without confidentiality constraints, our method achieves 10–100 \(\times \) acceleration.