.png){kind=icon}
.png){kind=icon}
Return
Single-server CPA-secure and post-quantum encrypted kNN queries
.png){kind=icon}
OA
AI
Z
J
J
DOI：10.1007/s12083-026-02267-x.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Encrypted \(\textit{k}\text {NN}\) query
Fully homomorphic encryption
CKKS
Post-quantum security
Query optimization
Memory-efficient implementation
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.6
Papers:
2.2K
Citations:
2.9K
Organization
Cited Papers