Computer scientists have designed an optimized homomorphic encryption framework that enables secure, chosen-plaintext-resilient, and post-quantum k-nearest neighbor queries over outsourced cloud databases using a single server. In a study published in the journal Peer-to-Peer Networking and Applications, researchers Zhiqiang Pan, Jungang Lou, and Jun Shao addressed a longstanding trade-off in privacy-preserving machine learning services between cryptographic security guarantees and real-world deployment practicality. Encrypted k-nearest neighbor computation functions as a core algorithmic primitive across classification, recommendation systems, and similarity search, where user queries must be evaluated against remote databases without exposing confidential features or records to untrusted service providers. Conventional architectures have historically struggled to reconcile robust confidentiality with practical deployment constraints, either compromising on formal security guarantees to maximize execution speed or imposing structural architectural requirements that prove fragile in operational distributed networks.
The fundamental conflict identified by the authors stems from the vulnerabilities inherent in prior single-server and multi-server query designs. Historically, most single-server encrypted similarity search protocols relied on asymmetric scalar-product-preserving encryption or asymmetric matrix encryption techniques. While schemes such as AME-kNN achieve millisecond-level query execution speeds by performing linear transformations over matrices, their security rests entirely on preserving the secrecy of the transformation matrix. When an adversary observes sufficient pairs of plaintexts and ciphertexts, algebraic reconstruction techniques can compromise the scheme, rendering such designs insecure against chosen-plaintext attacks or even known-plaintext attacks. Furthermore, these matrix transformations are based on classical mathematical assumptions that offer no cryptographic resilience against quantum cryptanalysis, where quantum algorithms such as Shor’s algorithm threaten integer factorization and discrete logarithm hardness assumptions.
To escape these single-server vulnerabilities, alternative constructions in the literature adopted multi-server configurations utilizing collaborative two-party computation, secret sharing, or garbled circuits to provide chosen-plaintext attack resistance. However, two-server models rely strictly on a non-collusion premise, assuming that separate administrative service providers will never share data or coordinate adversarial actions. In commercial cloud and distributed networked environments, economic alignment or shared operational infrastructure makes this non-collusion assumption particularly fragile, and collusion between servers completely collapses all confidentiality guarantees. In addition, multi-server approaches require continuous round-trip network communication between servers during runtime, introducing extensive synchronization delays and communication overhead that quickly become performance bottlenecks as datasets expand.
To overcome both architectural limitations, the researchers investigated lattice-based fully homomorphic encryption, specifically constructing single-server frameworks grounded in the CKKS scheme. CKKS supports approximate arithmetic over real and complex numbers by embedding data into cyclotomic polynomial rings and scales arithmetic operations via single-instruction-multiple-data slot batching. Its underlying cryptographic hardness derives from the ring learning with errors problem, which provides inherent resistance against both classical and quantum polynomial-time adversaries. To establish a baseline framework, the authors introduced MEHP-kNN, which adapts a secure total-sorting primitive known as MEHP to execute encrypted distance calculations, complete array ranking, and nearest-neighbor index recovery entirely within a single cloud environment without user interaction or multi-server assumptions.
The baseline MEHP-kNN pipeline operates across three successive homomorphic evaluation stages: squared Euclidean distance evaluation, full rank computation, and index extraction. First, an encrypted query vector is homomorphically replicated across matrix rows and subtracted from the encrypted database matrix before entry-wise squaring, avoiding non-linear square root operations while accurately preserving Euclidean distance orderings. Second, to rank all candidate records in parallel, the resulting distance column is expanded into row-wise and column-wise auxiliary matrices, enabling parallel evaluation of all pairwise record comparisons via a Chebyshev polynomial approximation of the non-linear comparison step. Finally, full index extraction replicates the calculated rank vector across an identity grid, subtracts constant rank values, and applies a high-degree indicator polynomial to locate zero-difference entries and output the top-k nearest records.
Although MEHP-kNN successfully delivers chosen-plaintext security and post-quantum protection on a single server, experimental profiling revealed that full sorting imposes severe computational penalties that hinder practical utility. When tested on a 128-dimensional synthetic dataset with a database size of 128 records, MEHP-kNN required 173 seconds of processing time and consumed approximately 17 gigabytes of system memory. Because MEHP-kNN reconstructs the full sorted order of the entire database before truncating down to the required k elements, the protocol accumulates polynomial approximation errors across every ranked slot. To counteract this cumulative error drift and guarantee correct record mapping, MEHP-kNN requires an extremely tight indicator approximation error bound between negative 0.5 over N and positive 0.5 over N, necessitating high polynomial degrees, deep multiplicative circuits, and oversized cryptographic parameter settings.
To resolve this performance barrier, the authors developed iMEHP-kNN, an optimized framework designed around the core structural requirement of similarity search: retrieving only the top-k nearest records rather than maintaining an exhaustively sorted list of every candidate in the database. By abandoning full-order reconstruction, iMEHP-kNN directly evaluates an approximate threshold indicator polynomial over the encrypted rank matrix to create a binary filter mask for all records whose assigned rank is less than or equal to k. Decrypting the masked index vector directly recovers the k nearest records. Because the protocol avoids sorting the remaining N minus k elements, it eliminates complex matrix transpositions and rotations while greatly suppressing error accumulation, allowing the admissible indicator approximation error tolerance to relax substantially to an interval between negative 0.5 and positive 0.5.
This error relaxation enables dramatic algorithmic and cryptographic optimizations within the underlying OpenFHE software implementation. By reducing the approximation constraints, iMEHP-kNN safely lowers the indicator polynomial degree to 196 using the Paterson-Stockmeyer evaluation algorithm, which bounds homomorphic multiplication depth and sharply reduces the required ciphertext modulus and ring dimension. While the baseline MEHP-kNN configuration exhibited a slot utilization rate of only 25 percent due to the disproportionate modulus sizes required for precision maintenance, iMEHP-kNN achieves 100 percent slot capacity utilization under standardized 128-bit security parameter sets. Consequently, ciphertexts require far fewer maintenance operations during algebraic multiplication, leading to immediate gains in memory economy and online transmission volume.
The authors verified both the algorithmic correctness and formal confidentiality of the optimized framework through rigorous mathematical proofs. In the semi-honest security model—where an untrusted single cloud server faithfully executes the prescribed protocol steps but inspects all intermediate ciphertext transcripts—the protocol bounds server-side data leakage strictly to a public tuple consisting of the database size N, the feature vector dimension d, and the query parameter k. Because the sequence of homomorphic operations, matrix dimensions, and ciphertext counts are completely deterministic and data-independent once this leakage tuple is fixed, a simulator can generate indistinguishable challenge transcripts from dummy plaintexts under the ring learning with errors assumption. The proof formally reduces the confidentiality of the entire query execution pipeline directly to the chosen-plaintext security of the underlying CKKS encryption scheme.
Empirical evaluations conducted on an Intel Core i7-14700KF server with 64 gigabytes of memory demonstrated substantial performance improvements across various database dimensions. For synthetic floating-point datasets spanning up to 16,384 entries across a 128-dimensional feature space, iMEHP-kNN achieved a 4-fold to 18-fold query runtime acceleration and a 12 percent to 33 percent reduction in peak memory consumption compared to MEHP-kNN. For a database of 128 records, iMEHP-kNN maintained an average query execution time of approximately 9.5 seconds while requiring only 2 gigabytes of memory, compared to the 173-second duration and 17-gigabyte memory footprint of the baseline. Furthermore, physical ciphertext serialization tests revealed that total online communication per query decreased from 334 megabytes under MEHP-kNN to 97 megabytes under iMEHP-kNN, demonstrating practical network transmission savings.
Despite these significant algorithmic gains over baseline fully homomorphic sorting, the researchers documented clear scalability constraints when evaluating larger dimensional spaces and record collections. Although iMEHP-kNN successfully validated the technical feasibility of single-server post-quantum queries up to 16,384 entries, the underlying pairwise comparison phase inherently scales with the number of mutual record interactions, causing memory consumption and rotation costs to expand rapidly beyond this threshold. Furthermore, when feature dimensions exceed the packing threshold permitted by the ring dimension—such as 512-dimensional to 2048-dimensional embeddings commonly used in modern retrieval tasks—feature vectors must be split across multiple ciphertext blocks, necessitating supplementary homomorphic aggregation steps that increase query latency.
To bridge the gap between proof-of-concept cryptographic kernels and million-scale commercial retrieval workloads, the researchers outlined several complementary avenues for future development. Proposed architectural enhancements include pairing homomorphic ranking with privacy-preserving pre-filtering mechanisms, such as encrypted locality-sensitive hashing or secure coarse clustering, to restrict intensive homomorphic evaluations to small candidate subsets. The authors also highlighted block-wise database sharding, client-side dimensionality reduction, and hardware-accelerated polynomial processing as critical steps to reduce computational bottlenecks, dynamic database updates, and evaluation over structured real-world machine learning benchmarks.
Subject of Research: Post-quantum single-server encrypted k-nearest neighbor query framework using CKKS homomorphic encryption
Article Title: Single-server CPA-secure and post-quantum encrypted kNN queries
Article References: Pan, Z., Lou, J., & Shao, J. (2026). Single-server CPA-secure and post-quantum encrypted kNN queries. Peer-to-Peer Networking and Applications, 19(4), Article 113. https://doi.org/10.1007/s12083-026-02267-x
Image Credits: AI Generated
DOI: 10.1007/s12083-026-02267-x
Keywords: encrypted search, k-nearest neighbors, homomorphic encryption, CKKS scheme, post-quantum cryptography, ring learning with errors, cloud computing, privacy-preserving machine learning, OpenFHE, single-server queries, chosen-plaintext attack, Chebyshev polynomials, Paterson-Stockmeyer algorithm, database security, Top-k index extraction, data privacy, secure computation
Cite Scienmag News
Katie Riggs. (November 21, 2026). Optimized Homomorphic Encryption Framework Secures Single-Server Post-Quantum Database Queries. Scienmag. https://scienmag.com/optimized-homomorphic-encryption-framework-secures-single-server-post-quantum-database-queries/
Katie Riggs. "Optimized Homomorphic Encryption Framework Secures Single-Server Post-Quantum Database Queries." Scienmag, 21 November 2026, https://scienmag.com/optimized-homomorphic-encryption-framework-secures-single-server-post-quantum-database-queries/. Accessed 21 November 2026.
Katie Riggs. "Optimized Homomorphic Encryption Framework Secures Single-Server Post-Quantum Database Queries." Scienmag. November 21, 2026. https://scienmag.com/optimized-homomorphic-encryption-framework-secures-single-server-post-quantum-database-queries/








