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.
