Saturday, November 21, 2026
Science
No Result
View All Result
  • Login
  • HOME
  • SCIENCE NEWS
  • CONTACT US
  • HOME
  • SCIENCE NEWS
  • CONTACT US
No Result
View All Result
Scienmag
No Result
View All Result
Home Science News

Optimized Homomorphic Encryption Framework Secures Single-Server Post-Quantum Database Queries

November 21, 2026
in Science News
Katie Riggs
By Katie Riggs Scienmag Editorial Profile - Quantum Physics
Reading Time: 6 mins read
0
Optimized Homomorphic Encryption Framework Secures Single-Server Post-Quantum Database Queries

Optimized Homomorphic Encryption Framework Secures Single-Server Post-Quantum Database Queries

65
SHARES
587
VIEWS
Share on FacebookShare on Twitter
ADVERTISEMENT

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/

Tags: Chebyshev polynomialschosen-plaintext attackCKKS schemecloud computingData Privacydatabase securityencrypted searchhomomorphic encryptionk-nearest neighborsOpenFHEPaterson-Stockmeyer algorithmpost-quantum cryptographyprivacy-preserving machine learningRing Learning with Errorssecure computationsingle-server queriesTop-k index extraction
Share26Tweet16
Previous Post

Ontological View of Human Dignity Challenges Functionalist Models in Healthcare Ethics

Next Post

Copper Oxide Doped Bismuth Vanadate Accelerates Visible Light Nitroaromatic Pollutant Degradation

Related Posts

Black Mulberry Dye Leads Performance in Green-Synthesized Titanium Dioxide Solar Cells
Science News

Black Mulberry Dye Leads Performance in Green-Synthesized Titanium Dioxide Solar Cells

November 21, 2026
Ancient Viral Remnants in the Human Genome Act as Double-Edged Cancer Regulators
Science News

Ancient Viral Remnants in the Human Genome Act as Double-Edged Cancer Regulators

November 21, 2026
Automated Sand Pluviation System Produces Uniform Deposits Using Constant Drop Height
Technology and Engineering

Automated Sand Pluviation System Produces Uniform Deposits Using Constant Drop Height

November 21, 2026
Global Multiple Myeloma Burden Rises While Forecasts Predict Declining Future Rates
Cancer

Global Multiple Myeloma Burden Rises While Forecasts Predict Declining Future Rates

November 21, 2026
Generalized Camassa-Holm Solutions Lose Hölder Regularity Over Time in Besov Spaces
Science News

Generalized Camassa-Holm Solutions Lose Hölder Regularity Over Time in Besov Spaces

November 21, 2026
Polar Bear Hair Inspires Scalable Biomass Aerogel Fibers for Thermal Insulation
Science News

Polar Bear Hair Inspires Scalable Biomass Aerogel Fibers for Thermal Insulation

November 21, 2026
Next Post
Copper Oxide Doped Bismuth Vanadate Accelerates Visible Light Nitroaromatic Pollutant Degradation

Copper Oxide Doped Bismuth Vanadate Accelerates Visible Light Nitroaromatic Pollutant Degradation

  • Mothers who receive childcare support from maternal grandparents show more optimized

    Mothers who receive childcare support from maternal grandparents show more parental warmth, finds NTU Singapore study

    27656 shares
    Share 11059 Tweet 6912
  • University of Seville Breaks 120-Year-Old Mystery, Revises a Key Einstein Concept

    1061 shares
    Share 424 Tweet 265
  • Bee body mass, pathogens and local climate influence heat tolerance

    682 shares
    Share 273 Tweet 171
  • Researchers record first-ever images and data of a shark experiencing a boat strike

    546 shares
    Share 218 Tweet 137
  • Groundbreaking Clinical Trial Reveals Lubiprostone Enhances Kidney Function

    531 shares
    Share 212 Tweet 133
Science

Embark on a thrilling journey of discovery with Scienmag.com—your ultimate source for cutting-edge breakthroughs. Immerse yourself in a world where curiosity knows no limits and tomorrow’s possibilities become today’s reality!

RECENT NEWS

  • Black Mulberry Dye Leads Performance in Green-Synthesized Titanium Dioxide Solar Cells
  • Ancient Viral Remnants in the Human Genome Act as Double-Edged Cancer Regulators
  • Automated Sand Pluviation System Produces Uniform Deposits Using Constant Drop Height
  • Global Multiple Myeloma Burden Rises While Forecasts Predict Declining Future Rates

Categories

  • Agriculture
  • Anthropology
  • Archaeology
  • Athmospheric
  • Biology
  • Biotechnology
  • Blog
  • Bussines
  • Cancer
  • Chemistry
  • Climate
  • Earth Science
  • Editorial Policy
  • Marine
  • Mathematics
  • Medicine
  • Pediatry
  • Policy
  • Psychology & Psychiatry
  • Science Education
  • Science News
  • Social Science
  • Space
  • Technology and Engineering

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 5,151 other subscribers

© 2026 Scienmag - Science Magazine

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
No Result
View All Result
  • HOME
  • SCIENCE NEWS
  • CONTACT US

© 2026 Scienmag - Science Magazine

Discover more from Science

Subscribe now to keep reading and get access to the full archive.

Continue reading