Efficient Arithmetic-and-Comparison Homomorphic Encryption with Space Switching

• URL: http://arxiv.org/abs/2604.19890v1
• Date: Tue, 21 Apr 2026 18:12:37 GMT
• Title: Efficient Arithmetic-and-Comparison Homomorphic Encryption with Space Switching
• Abstract summary: homomorphic encryption (FHE) enables computation on encrypted data without decryption.<n>No existing scheme efficiently supports both arithmetic and comparison operations in a unified framework.<n>We propose space switching method to integrate arithmetic and comparison seamlessly within FV-style schemes.
• Score: 15.580543805873466
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Fully homomorphic encryption (FHE) enables computation on encrypted data without decryption, making it central to privacy-preserving applications. However, no existing scheme efficiently supports both arithmetic and comparison operations in a unified framework. Prior approaches such as scheme switching and polynomial approximation face serious limitations: switching incurs prohibitive overhead for large inputs, while approximation methods introduce errors near critical points, restricting use in accuracy-sensitive tasks. We propose space switching method to integrate arithmetic and comparison computation seamlessly within FV-style schemes. Our approach identifies that the two types of operations require different plaintext spaces and introduces two procedures: a reduction step to transition from the number space $\mathbb{Z}_{p^r}$ to the digit space $\mathbb{Z}_{p}$, and a modulus-raising step to map results back to $\mathbb{Z}_{p^r}$. This design enables continuous evaluation of arithmetic and comparison within the same scheme. Experiments show that our method achieves up to $17\times$ faster performance than scheme switching and $15\times$ faster than direct comparison on database workloads, demonstrating its practicality for real-world privacy-preserving computation. Code and artifacts are available at https://github.com/UCF-Lou-Lab-PET/Universal-BGV.

Related papers

• HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation [56.14416807766864]
  Homomorphic encryption allows a server to run a language model directly on encrypted user prompts.<n>Existing approaches fix the iteration counts uniformly across the model rather than tailoring them to each site's error tolerance.<n>We introduce Homomorphic Encryption-Aware Training (HEAT), a fine-tuning method that makes the per-nonline iteration counts learnable.
  arXiv  Detail & Related papers  (2026-09-01T18:02:02Z)
• Bootstrapping as a Morphism: An Arithmetic Geometry Approach to Asymptotically Faster Homomorphic Encryption [0.9179857807576733]
  This paper introduces a new approach to bootstrapping that completely bypasses the traditional circuit evaluation model.<n>We apply the tools of modern arithmetic geometry to reframe the bootstrapping operation as a direct geometric projection.<n>Our work is a complete and provably correct bootstrapping algorithm with a computational complexity of $O(d cdot textpoly(log q))$, where $d$ is the ring dimension and $q$ is the ciphertext.
  arXiv  Detail & Related papers  (2025-09-29T03:39:01Z)
• Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell [9.554839026375568]
  Edit distance computations are essential in applications across finance and genomics, such as DNA sequence alignment.<n>We introduce an optimised algorithm that significantly reduces the cost of edit distance calculations called Leuvenshtein.
  arXiv  Detail & Related papers  (2025-08-20T09:40:06Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Efficient Ranking, Order Statistics, and Sorting under CKKS [5.543544712471747]
  Homomorphic Encryption (FHE) enables operations on encrypted data, making it extremely useful for privacy-preserving applications.<n>The high computational overhead and limited native operations of FHE pose significant challenges for an efficient implementation of these tasks.<n>We present solutions for ranking, order statistics, and sorting, that achieve a comparison depth of up to 2 (constant)
  arXiv  Detail & Related papers  (2024-12-19T18:06:25Z)
• BoostCom: Towards Efficient Universal Fully Homomorphic Encryption by Boosting the Word-wise Comparisons [14.399750086329345]
  Fully Homomorphic Encryption (FHE) allows for the execution of computations on encrypted data without the need to decrypt it first. In this paper, we introduce BoostCom, a scheme designed to speed up word-wise comparison operations. We achieve an end-to-end performance improvement of more than an order of magnitude (11.1x faster) compared to the state-of-the-art CPU-based uFHE systems.
  arXiv  Detail & Related papers  (2024-07-10T02:09:10Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  We present Hierarchical cOntext MERging (HOMER), a new training-free scheme designed to overcome the limitations of large language models. HomeR uses a divide-and-conquer algorithm, dividing long inputs into manageable chunks. A token reduction technique precedes each merging, ensuring memory usage efficiency.
  arXiv  Detail & Related papers  (2024-04-16T06:34:08Z)
• Low-Complexity Integer Divider Architecture for Homomorphic Encryption [5.857929080874288]
  Homomorphic encryption (HE) allows computations to be directly carried out on ciphertexts and enables privacy-preserving cloud computing. An algorithm is proposed to compute the quotient and vigorous mathematical proofs are provided.
  arXiv  Detail & Related papers  (2024-01-19T23:53:59Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.