Privacy-Preserving Approximate Nearest Neighbor Search on High-Dimensional Data

Hui Li; Jeffrey Xu Yu; Jiadong Xie; Jiangtao Cui; Yandi Zhang; Yingfan Liu

REVIEW 3 major objections 2 minor 1 cited by

Privacy-Preserving Approximate Nearest Neighbor Search on High-Dimensional Data

T0 review · 3 major / 2 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims a single-server privacy-preserving nearest-neighbor search that compares encrypted distances exactly and runs up to 1000x faster, but the supplied full text is a different manuscript.

desk verdict The abstract advertises a PP-ANNS system with a new encryption primitive, but the full text is an unrelated HAR paper, so the submission is un-reviewable as-is. read the letter →

arxiv 2508.10373 v1 pith:CPMGW5CR submitted 2025-08-14 cs.DB

Yingfan Liu , Yandi Zhang , Jiadong Xie , Hui Li , Jeffrey Xu Yu , Jiangtao Cui This is my paper

classification cs.DB

keywords privacy-preservingk-ANNSdistancecomparisonencryptionencryptedsimilaritysearchsingle-serversecurecomputationfilter-and-refinehigh-dimensionalvectorsclouddataoutsourcing

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims to solve privacy-preserving approximate k-nearest-neighbor (k-ANNS) search on high-dimensional data using a single untrusted cloud server. Its proposed mechanism is a new 'distance comparison encryption' that the abstract says supports secure, efficient, and exact distance comparisons on ciphertexts, plus a privacy-preserving index and a filter-and-refine search built to keep accuracy while cutting latency. The abstract reports a security analysis and experiments claiming up to three orders of magnitude speedup over previous PP-ANNS methods at the same accuracy. The full text supplied with the submission, however, is a different paper on few-shot human activity recognition with visual reinforcement learning, so the PP-ANNS construction, its security proof, and its benchmark results have no derivable support in the document as provided.

What carries the argument

The central object is distance comparison encryption, an encryption scheme that supposedly lets an untrusted server compare distances between encrypted high-dimensional vectors and return exact comparison results without learning the vectors or the distance order. It is the load-bearing primitive: exact ciphertext comparisons preserve search accuracy, while the encryption is meant to provide the privacy guarantee. The second mechanism is the privacy-preserving index, which combines an approximate nearest-neighbor method with approximate distance computation; the filter-and-refine search first narrows candidates on the encrypted index and then refines with exact encrypted distance comparisons

What would settle it

Try to instantiate distance comparison encryption from any concrete scheme and test whether the server can infer relative distances or recover vector values by correlating repeated encrypted comparisons. If such leakage exists, the security claim is false; if no construction can be supplied at all, the claimed speedup is untestable. A reader could also simply check whether the actual full version of the PP-ANNS paper contains the construction, proof, and benchmarks promised in the abstract.

Watch

Extended reading notes

Core claim

The abstract's central claim is that PP-ANNS can be run mainly on one cloud server, avoiding heavy user-server communication, by encrypting vectors so that the server can perform exact distance comparisons without seeing the data. The authors say they build a privacy-preserving index that couples an approximate nearest-neighbor method with approximate distance computation, and search it with a filter-and-refine strategy. They further claim this preserves accuracy while accelerating search by up to three orders of magnitude relative to existing PP-ANNS methods, backed by a security analysis. As supplied, the document's full text does not contain any of this: it presents a separate few-shot hu

Load-bearing premise

The whole approach stands or falls on whether distance comparison encryption can compare encrypted distances exactly while keeping the vectors and their distance order hidden from the server, and still be cheap enough to run inside an approximate nearest-neighbor index.

Editorial extensions

If this is right

A single untrusted server could answer k-ANNS queries over encrypted vectors with no per-query interaction from the data owner, removing the communication bottleneck of current two-party protocols.
Encrypted search would keep the accuracy of unencrypted approximate search, because exact distance comparisons on ciphertexts drive the refinement stage.
Search latency would drop by up to three orders of magnitude relative to current PP-ANNS methods, making encrypted high-dimensional similarity search practical at scale.
Data owners could outsource vectors once and let multiple users query them, with a security analysis bounding what the server learns.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the claimed combination of exact ciphertext distance comparisons with no leakage of distance order sits in tension with known primitives such as order-revealing encryption, which typically trades order leakage for comparability. The scheme would need a novel construction to escape that tension.
Editorial inference: because the supplied body is a different manuscript, the abstract's claims cannot currently be checked; a reader should treat the PP-ANNS contribution as an unsubstantiated proposal rather than a demonstrated result.
Editorial inference: if the primitive were real, the same filter-and-refine structure would likely transfer to other encrypted geometric queries, such as range search, clustering, or outlier detection on outsourced high-dimensional data.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the manuscript you sent me is two different papers glued together by an error. The title and abstract advertise a privacy-preserving approximate nearest neighbor search system with a new 'distance comparison encryption' primitive, a single-server index, and speedups of up to three orders of magnitude. The full text is an unrelated paper on few-shot human activity recognition using GRPO-based reinforcement learning on multimodal LLMs (FAVOR). There is nothing in the body about encryption, ANNS, a security proof, or any vector search experiments. So the central claim has zero support in the submitted document.

What is actually good: the FAVOR portion, taken on its own, is a coherent empirical paper. It applies GRPO to Qwen2.5-VL for HAR, defines a verifiable reward with accuracy and format components, and reports consistent gains over SFT and baseline on UCF50/UCF101/UCF-Crime/HMDB51 across 1- to 16-shot settings. The ablation on number of responses and frozen vision modules is a nice touch. If this were submitted as a HAR paper, it would be a decent incremental contribution, though not a breakthrough.

But for the paper as submitted, the disconnect is terminal. The abstract's core claims—exact distance comparisons on ciphertexts, a privacy-preserving index, a filter-and-refine search, security analysis, and 1000x speedups—are not merely under-supported; they are completely absent. There is no derivation, no protocol, no theorem, and no experiment that touches the claimed subject. The equations in Section III are GRPO reward and KL-divergence formulas, not cryptographic constructions. The experiments in Section IV report accuracy on HAR datasets, not ANNS latency or recall.

I don't see any circularity or hidden fitting in the HAR portion; that part is straightforwardly empirical. But the mismatch between the abstract and the body makes the whole artifact un-reviewable. Whether this is a submission pipeline error or something else, a serious editor should not send this to referees. The correct action is to desk reject and ask the authors to resubmit the correct manuscript.

Recommendation: don't spend referee time on this. If the authors fix the artifact and the real PP-ANNS paper exists, it might be worth a look—the abstract's idea of exact distance comparison encryption is intriguing and, if true, would be a meaningful practical advance. But this submission is not it.

Referee Report

3 major / 2 minor

Summary. The abstract of arXiv:2508.10373 announces a privacy-preserving approximate nearest neighbor (PP-ANNS) scheme built on a new primitive called 'distance comparison encryption,' claiming exact distance comparisons on ciphertexts, a single-server encrypted index, a filter-and-refine search method, a security analysis, and experimental speedups of up to three orders of magnitude with no loss of accuracy. The supplied full text, however, is a paper on few-shot human activity recognition (FAVOR), using multimodal LLMs and GRPO, with equations for RLVR rewards and KL divergence and experiments on UCF50/UCF101/UCF-Crime/HMDB51. None of the PP-ANNS material—the encryption scheme, the index, the search protocol, the security model, or the experiments—appears anywhere in the manuscript.

Significance. If the claimed construction were present and correct, the paper could be of substantial practical importance: a single-server PP-ANNS protocol with exact encrypted distance comparisons and a large speedup would address a recognized bottleneck in outsourced vector search. However, the submitted manuscript provides no construction, no proof, and no evaluation of that claim. The significance therefore cannot be assessed from the text; the only assessable content is an unrelated HAR paper.

major comments (3)

[Full text, §§III–IV] The body of the submitted manuscript is a different paper: arXiv:2508.10371, a few-shot human activity recognition paper. Section III defines GRPO rewards and KL-divergence objectives; Section IV reports accuracy on UCF50, UCF101, UCF-Crime, and HMDB51. There is no definition of distance comparison encryption, no description of a privacy-preserving index, no search algorithm, and no PP-ANNS experiment. The central claim of the abstract is therefore unsupported by any derivation or data in the submitted text.
[Abstract / §III] The core primitive, 'distance comparison encryption,' is never defined. No encryption scheme, key generation, ciphertext comparison procedure, leakage profile, or security notion is stated. The equations in Section III (Eqs. (1)–(5)) are the RLVR reward, KL-regularized objective, and classification reward; they do not relate to distance comparisons. Since the primitive is the load-bearing element of the proposed method, the omission is fatal to the paper's technical claim.
[Abstract / §IV] The claimed experimental results—'up to 3 orders of magnitude' speedup over state-of-the-art PP-ANNS methods while preserving accuracy—have no counterpart in Section IV. That section reports few-shot recognition accuracy for HAR datasets and contains no ANNS baselines, latency measurements, recall/precision comparisons, or privacy experiments. The speedup claim is therefore not just unverified; it is unverifiable from the supplied manuscript.

minor comments (2)

[Metadata] The full text carries arXiv identifier 2508.10371v1 [cs.RO], while the manuscript under review is identified as arXiv:2508.10373 (cs.DB). This identifier mismatch should be resolved; it is likely a submission error.
[References] The reference list is entirely oriented to human activity recognition and multimodal LLMs; no cryptography, secure computation, or approximate nearest neighbor search references appear. If the correct manuscript is intended, reference handling needs a full revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity detectable: the supplied full text is an unrelated HAR paper, so the claimed PP-ANNS derivation chain is absent rather than circular.

full rationale

The abstract claims a PP-ANNS construction with distance comparison encryption, a single-server privacy-preserving index, filter-and-refine search, security analysis, and up to 3 orders of magnitude speedup. However, the supplied full text is a different paper on few-shot human activity recognition using MLLM/GRPO. None of the abstract's components appear in the body: there is no definition of distance comparison encryption, no encrypted index, no search algorithm, no security proof, and no PP-ANNS experiments. Circularity requires a derivation or prediction that reduces by construction to its own inputs, e.g., a fitted parameter renamed as a prediction or a self-citation chain that forces a conclusion. Because no part of the claimed derivation chain is present, there is no equation, fitted value, or cited prior result that could be shown to be equivalent to the conclusion. A mismatch between abstract and body is a serious integrity/audit concern, but it is not a circularity finding. Therefore, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 2 assumptions · 1 invented entities

The central claim depends entirely on an encryption primitive that is named but not defined, and on a threat model that is not specified. Because the body text is unrelated to the abstract, the ledger cannot be completed from actual content; these entries are inferred from the abstract alone.

assumptions (2)

ad hoc to paper Distance comparison encryption exists and admits exact comparison on ciphertexts.
Introduced in the abstract as 'a novel encryption method'; no construction or proof is provided in the supplied text.
domain assumption A single untrusted server can execute the filter-and-refine protocol without learning vector contents or distance order.
Abstract's design goal; standard security assumption but unstated formally in the supplied document.

invented entities (1)

distance comparison encryption
purpose: Enable exact distance comparisons on encrypted high-dimensional vectors on a single cloud server
Named in the abstract as the key novelty; no algorithm, security reduction, or falsifiable prediction is given in the supplied full text.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Privacy-Preserving Approximate Nearest Neighbor Search on High-Dimensional Data." pith.science (2026). https://pith.science/paper/CPMGW5CR

@misc{pith2026250810373,
  author       = {Pith},
  title        = {Pith review of: Privacy-Preserving Approximate Nearest Neighbor Search on High-Dimensional Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CPMGW5CR}},
  note         = {Machine review of arXiv:2508.10373}
}

abstract

In the era of cloud computing and AI, data owners outsource ubiquitous vectors to the cloud, which furnish approximate $k$-nearest neighbors ($k$-ANNS) services to users. To protect data privacy against the untrusted server, privacy-preserving $k$-ANNS (PP-ANNS) on vectors has been a fundamental and urgent problem. However, existing PP-ANNS solutions fall short of meeting the requirements of data privacy, efficiency, accuracy, and minimal user involvement concurrently. To tackle this challenge, we introduce a novel solution that primarily executes PP-ANNS on a single cloud server to avoid the heavy communication overhead between the cloud and the user. To ensure data privacy, we introduce a novel encryption method named distance comparison encryption, facilitating secure, efficient, and exact distance comparisons. To optimize the trade-off between data privacy and search performance, we design a privacy-preserving index that combines the state-of-the-art $k$-ANNS method with an approximate distance computation method. Then, we devise a search method using a filter-and-refine strategy based on the index. Moreover, we provide the security analysis of our solution and conduct extensive experiments to demonstrate its superiority over existing solutions. Based on our experimental results, our method accelerates PP-ANNS by up to 3 orders of magnitude compared to state-of-the-art methods, while not compromising the accuracy.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Clicks Versus Conversion: Choosing a Recommender's Training Objective in E-Commerce
cs.IR 2025-08 unverdicted novelty 5.0 of 10

Training an e-commerce recommender on order-submit rate instead of click-through rate lifted GMV more than five times as much in a live A/B test, with no measured loss in product discovery.

Reference graph

Works this paper leans on

22 extracted references · 10 canonical work pages · cited by 1 Pith paper

[1]

Qwen2.5-vl technical report

Shuai Bai, Keqin Chen, Xuejing Liu, Jialin Wang, Wenbin Ge, Sibo Song, Kai Dang, Peng Wang, Shijie Wang, Jun Tang, et al. Qwen2.5-vl technical report. arXiv preprint arXiv:2502.13923 , 2025

arXiv 2025
[2]

Marwa R. M. Bastwesy, Hyuckjin Choi, and Yutaka Arakawa. Tracking on-desk gestures based on wi-fi csi on low-cost microcontroller. In In- ternational Conference on Mobile Computing and Ubiquitous Network , pages 1–6, 2023

work page 2023
[3]

Openvlthinker: An early exploration to complex vision-language reasoning via iterative self-improvement

Yihe Deng, Hritik Bansal, Fan Yin, Nanyun Peng, Wei Wang, and Kai-Wei Chang. Openvlthinker: An early exploration to complex vision-language reasoning via iterative self-improvement. arXiv preprint arXiv:2503.17352, 2025

arXiv 2025
[4]

Deepseek-r1: Incentivizing reasoning capability in llms via reinforce- ment learning

Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforce- ment learning. arXiv preprint arXiv:2501.12948 , 2025

arXiv 2025
[5]

Open-reasoner-zero: An open source approach to scaling up reinforcement learning on the base model

Jingcheng Hu, Yinmin Zhang, Qi Han, Daxin Jiang, Xiangyu Zhang, and Heung-Yeung Shum. Open-reasoner-zero: An open source approach to scaling up reinforcement learning on the base model. arXiv preprint arXiv:2503.24290, 2025

arXiv 2025
[6]

Efficient multimodal large language models: A survey

Yizhang Jin, Jian Li, Yexin Liu, Tianjun Gu, Kai Wu, Zhengkai Jiang, Muyang He, Bo Zhao, Xin Tan, Zhenye Gan, et al. Efficient multimodal large language models: A survey. arXiv preprint arXiv:2405.10739 , 2024

arXiv 2024
[7]

Hmdb: A large video database for human motion recognition

Hildegard Kuehne, Hueihan Jhuang, Est ´ıbaliz Garrote, Tomaso Poggio, and Thomas Serre. Hmdb: A large video database for human motion recognition. In International Conference on Computer Vision , pages 2556–2563, 2011

work page 2011
[8]

Komal Kumar, Tajamul Ashraf, Omkar Thawakar, Rao Muhammad Anwer, Hisham Cholakkal, Mubarak Shah, Ming-Hsuan Yang, Phillip H. S. Torr, Fahad Shahbaz Khan, and Salman Khan. Llm post-training: A deep dive into reasoning large language models. arXiv preprint arXiv:2502.21321, 2025

arXiv 2025

Show all 22 references

[9]

Surveying the mllm landscape: A meta-review of current surveys

Ming Li, Keyu Chen, Ziqian Bi, Ming Liu, Benji Peng, Qian Niu, Junyu Liu, Jinlang Wang, Sen Zhang, Xuanhe Pan, et al. Surveying the mllm landscape: A meta-review of current surveys. arXiv preprint arXiv:2409.18991, 2024

2024
[10]

Visual-rft: Visual reinforcement fine- tuning

Ziyu Liu, Zeyi Sun, Yuhang Zang, Xiaoyi Dong, Yuhang Cao, Haodong Duan, Dahua Lin, and Jiaqi Wang. Visual-rft: Visual reinforcement fine- tuning. arXiv preprint arXiv:2503.01785 , 2025

2025 arXiv
[11]

A comprehensive overview of large language models

Humza Naveed, Asad Ullah Khan, Shi Qiu, Muhammad Saqib, Saeed Anwar, Muhammad Usman, Naveed Akhtar, Nick Barnes, and Ajmal Mian. A comprehensive overview of large language models. arXiv preprint arXiv:2307.06435, 2023

2023 arXiv
[12]

A review of aiot-based human activity recognition: From application to technique

Wen Qi, Xiangmin Xu, Kun Qian, Bj ¨orn W Schuller, Giancarlo Fortino, and Andrea Aliverti. A review of aiot-based human activity recognition: From application to technique. IEEE Journal of Biomedical and Health Informatics, 29(4):2425–2438, 2024

2024
[13]

Recognizing 50 human action categories of web videos

Kishore K Reddy and Mubarak Shah. Recognizing 50 human action categories of web videos. Machine Vision and Applications, 24(5):971– 981, 2013

2013
[14]

Vlm-r1: A stable and generalizable r1-style large vision-language model

Haozhan Shen, Peng Liu, Jingcheng Li, Chunxin Fang, Yibo Ma, Jiajia Liao, Qiaoli Shen, Zilun Zhang, Kangjia Zhao, Qianqian Zhang, et al. Vlm-r1: A stable and generalizable r1-style large vision-language model. arXiv preprint arXiv:2504.07615 , 2025

2025 arXiv
[15]

Ucf101: A dataset of 101 human actions classes from videos in the wild

Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah. Ucf101: A dataset of 101 human actions classes from videos in the wild. arXiv preprint arXiv:1212.0402, 2012

2012 arXiv
[16]

K. Suda, S. Ishida, and H. Inamura. User estimation with touch panel buttons toward in-home activity recognition. In 2023 Fourteenth In- ternational Conference on Mobile Computing and Ubiquitous Network , pages 1–6, Kyoto, Japan, 2023

2023
[17]

Real-world anomaly detection in surveillance videos

Waqas Sultani, Chen Chen, and Mubarak Shah. Real-world anomaly detection in surveillance videos. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6479–6488, 2018

2018
[18]

Human action recognition from various data modalities: A review

Zehua Sun, Qiuhong Ke, Hossein Rahmani, Mohammed Bennamoun, Gang Wang, and Jun Liu. Human action recognition from various data modalities: A review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):3200–3225, 2022

2022
[19]

A systematic review of human activity recognition based on mobile devices: overview, progress and trends

Yafeng Yin, Lei Xie, Zhiwei Jiang, Fu Xiao, Jiannong Cao, and Sanglu Lu. A systematic review of human activity recognition based on mobile devices: overview, progress and trends. IEEE Communications Surveys & Tutorials, 26(2):890–929, 2024

2024
[20]

R1-omni: Explainable omni- multimodal emotion recognition with reinforcement learning

Jiaxing Zhao, Xihan Wei, and Liefeng Bo. R1-omni: Explainable omni- multimodal emotion recognition with reinforcement learning. arXiv preprint arXiv:2503.05379, 2025

2025 arXiv
[21]

Dynamic graph memory bank for video inpainting

Xiaoqiang Zhou, Chaoyou Fu, Huaibo Huang, and Ran He. Dynamic graph memory bank for video inpainting. IEEE Transactions on Circuits and Systems for Video Technology , 34(11):10831–10844, 2024

2024
[22]

Ristra: Re- cursive image super-resolution transformer with relativistic assessment

Xiaoqiang Zhou, Huaibo Huang, Zilei Wang, and Ran He. Ristra: Re- cursive image super-resolution transformer with relativistic assessment. IEEE Transactions on Multimedia , 26:6475–6487, 2024

2024

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

Qwen2.5-vl technical report

Shuai Bai, Keqin Chen, Xuejing Liu, Jialin Wang, Wenbin Ge, Sibo Song, Kai Dang, Peng Wang, Shijie Wang, Jun Tang, et al. Qwen2.5-vl technical report. arXiv preprint arXiv:2502.13923 , 2025

arXiv 2025

[2] [2]

Marwa R. M. Bastwesy, Hyuckjin Choi, and Yutaka Arakawa. Tracking on-desk gestures based on wi-fi csi on low-cost microcontroller. In In- ternational Conference on Mobile Computing and Ubiquitous Network , pages 1–6, 2023

work page 2023

[3] [3]

Openvlthinker: An early exploration to complex vision-language reasoning via iterative self-improvement

Yihe Deng, Hritik Bansal, Fan Yin, Nanyun Peng, Wei Wang, and Kai-Wei Chang. Openvlthinker: An early exploration to complex vision-language reasoning via iterative self-improvement. arXiv preprint arXiv:2503.17352, 2025

arXiv 2025

[4] [4]

Deepseek-r1: Incentivizing reasoning capability in llms via reinforce- ment learning

Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforce- ment learning. arXiv preprint arXiv:2501.12948 , 2025

arXiv 2025

[5] [5]

Open-reasoner-zero: An open source approach to scaling up reinforcement learning on the base model

Jingcheng Hu, Yinmin Zhang, Qi Han, Daxin Jiang, Xiangyu Zhang, and Heung-Yeung Shum. Open-reasoner-zero: An open source approach to scaling up reinforcement learning on the base model. arXiv preprint arXiv:2503.24290, 2025

arXiv 2025

[6] [6]

Efficient multimodal large language models: A survey

Yizhang Jin, Jian Li, Yexin Liu, Tianjun Gu, Kai Wu, Zhengkai Jiang, Muyang He, Bo Zhao, Xin Tan, Zhenye Gan, et al. Efficient multimodal large language models: A survey. arXiv preprint arXiv:2405.10739 , 2024

arXiv 2024

[7] [7]

Hmdb: A large video database for human motion recognition

Hildegard Kuehne, Hueihan Jhuang, Est ´ıbaliz Garrote, Tomaso Poggio, and Thomas Serre. Hmdb: A large video database for human motion recognition. In International Conference on Computer Vision , pages 2556–2563, 2011

work page 2011

[8] [8]

Komal Kumar, Tajamul Ashraf, Omkar Thawakar, Rao Muhammad Anwer, Hisham Cholakkal, Mubarak Shah, Ming-Hsuan Yang, Phillip H. S. Torr, Fahad Shahbaz Khan, and Salman Khan. Llm post-training: A deep dive into reasoning large language models. arXiv preprint arXiv:2502.21321, 2025

arXiv 2025