I think the paper is overclaiming the privacy story by treating randomized response on binary codes as a substitute for real query privacy. > HE was too slow. Sure, HE is slow here, but swapping it for a probabilistic encoding of the embedding doesnt make the access pattern go away, and thats the part an attacker actually cares about in ANN search (what gets touched, how often, how the graph walk concentrates). If the server still sees the candidate set and the graph traversal shape, you have a noisy search pipeline, not private search in the usual sense. For a lot of these systems the uncomfortable truth is just: you can hide some bits of the vector, or you can keep the retrieval accurate, but you dont get to pretend those are the same property ...