Paper 2026/1397

HANNS: Low-Storage Non-Interactive Approximate Private Nearest Neighbor Search with Sublinear Comparison Complexity

Abstract

With growing concerns over data privacy, private nearest neighbors search (PNNS) attracts increasing research attention. Existing PNNS follow two main approaches: i) interactive PNNS based on secure multi-party computation protocols that leverage index structures to achieve sublinear complexity, and ii) non-interactive PNNS utilizing fully homomorphic encryption to minimize communication bandwid that the cost of superlinear computational complexity. To address the communication-computation dilemma, we propose HANNS, a non-interactive PNNS protocol with a sublinear number of encrypted comparisons. Our key observation is that, while the full-table scan is inevitable under the non-interactive setting, the number of costly encrypted comparisons can be significantly reduced. Specifically, we develop a cluster ordering scheme over FHE that leverages a segmented rigid transformation to obliviously identify candidate clusters with only a sublinear number of homomorphic comparisons. Furthermore, we introduce a homomorphic product quantization (PQ) scheme that enables coarse search and reranking over PQ-encoded vectors, which significantly reduces the computational and storage overheads. In the experiment, we show that HANNS achieves 41x to 277x speedup and a storage reduction of 12x to 31.7x compared to the most recent non-interactive schemes, while reducing communication by 1,258x to 80,536x and achieving a speedup of 8x to 119x over interactive schemes in low-bandwidth scenarios.