Single-server CPA-secure and post-quantum encrypted kNN queries

As a fundamental primitive in privacy-preserving machine learning as a service, encrypted k-nearest neighbors ( $$\textit{k}\text {NN}$$ ) should ideally provide strong confidentiality guarantees while remaining practical for cloud deployment. However, existing schemes often face a trade-off between security and deployability: many single-server solutions do not achieve chosen-plaintext security, whereas stronger constructions typically rely on non-colluding multi-server assumptions. In addition, most existing designs are based on classical hardness assumptions and therefore do not offer post-quantum resilience. To address these limitations, we present $$\mathtt {MEHP\text {-}kNN}$$ , a single-server encrypted $$\textit{k}\text {NN}$$ framework built on secure sorting under $$\texttt{CKKS}$$ -based fully homomorphic encryption. To the best of our knowledge, this framework is among the first in the considered setting to jointly target single-server deployment, chosen-plaintext confidentiality, and post-quantum security based on RLWE assumptions. Since the direct construction incurs high computational and memory overhead, we further propose $$\mathtt {iMEHP\text {-}kNN}$$ , an optimized Top-k query framework that removes homomorphic operations unnecessary for full sorting and reduces the cost of indicator-function evaluation through a refined polynomial design. We implement both schemes using OpenFHE and evaluate them under practical parameter settings. Experimental results show that, for a 128-dimensional feature space and a database of up to 16,384 entries, $$\mathtt {iMEHP\text {-}kNN}$$ achieves a 4 $$\times $$ to 18 $$\times $$ runtime improvement and a 12% to 33% reduction in memory usage compared with the $$\mathtt {MEHP\text {-}kNN}$$ baseline. These results improve the practical feasibility of secure single-server encrypted $$\textit{k}\text {NN}$$ queries in outsourced cloud environments.