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 ( kNN ) 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 MEHP-kNN , a single-server encrypted kNN framework built on secure sorting under 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 iMEHP-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, iMEHP-kNN achieves a 4 × to 18 × runtime improvement and a 12% to 33% reduction in memory usage compared with the MEHP-kNN baseline. These results improve the practical feasibility of secure single-server encrypted kNN queries in outsourced cloud environments.