Low-Complexity Integer Divider Architecture for Homomorphic Encryption

• URL: http://arxiv.org/abs/2401.11064v1
• Date: Fri, 19 Jan 2024 23:53:59 GMT
• Title: Low-Complexity Integer Divider Architecture for Homomorphic Encryption
• Authors: Sajjad Akherati, Jiaxuan Cai, Xinmiao Zhang,
• Abstract summary: 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.
• Score: 5.857929080874288
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Homomorphic encryption (HE) allows computations to be directly carried out on ciphertexts and enables privacy-preserving cloud computing. The computations on the coefficients of the polynomials involved in HE are always followed by modular reduction, and the overall complexity of ciphertext multiplication can be reduced by utilizing the quotient. Our previous design considers the cases that the dividend is an integer multiple of the modulus and the modulus is in the format of $2^w-2^u\pm1$, where $u<w/2$. In this paper, the division is generalized for larger $u$ and dividend not an integer multiple of the modulus. An algorithm is proposed to compute the quotient and vigorous mathematical proofs are provided. Moreover, efficient hardware architecture is developed for implementing the proposed algorithm. Compared to alternative division approaches that utilize the inverse of the divisor, for $w=32$, the proposed design achieves at least 9% shorter latency and 79\% area reduction for 75% possible values of $u$.

Related papers

• A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions [0.0]
  We aim to advance the state-of-the-art in Quadratic Unconstrained Binary Optimization formulation with a focus on cryptography algorithms. We consider the most widespread cryptography algorithms including AES-128/192/256, MD5, SHA1 and SHA256. For each of these, we achieved QUBO instances reduced by thousands of logical variables compared to previously published results, while keeping the QUBO matrix sparse and the magnitude of the coefficients low.
  arXiv  Detail & Related papers  (2024-09-10T18:46:26Z)
• Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach [3.0079490585515343]
  We introduce a modular arithmetic approach to the Subset Sum problem. We show that density guarantees can be improved by analysing the lengths of the LLL reduced basis vectors.
  arXiv  Detail & Related papers  (2024-08-28T19:32:14Z)
• 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)
• Computing $\varphi(N)$ for an RSA module with a single quantum query [0.0]
  We give a computation time algorithm to compute $varphi(N)$ for an RSA module $N$ using as input the order modulo $N$ of a randomly chosen integer.
  arXiv  Detail & Related papers  (2024-06-06T13:30:18Z)
• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation. We obtain several improved algorithms for private optimization problems, including decomposable submodular and set algorithm cover.
  arXiv  Detail & Related papers  (2024-05-28T19:02:30Z)
• A new lightweight additive homomorphic encryption algorithm [0.0]
  This article describes a lightweight additive homomorphic algorithm with the same encryption and decryption keys. It reduces the computational cost of encryption and decryption from modular exponentiation to modular multiplication.
  arXiv  Detail & Related papers  (2023-12-12T05:12:20Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  This paper aims to design a new gradient coding scheme for mitigating partial stragglers in distributed learning. We propose a gradient coordinate coding scheme with L coding parameters representing L possibly different diversities for the L coordinates, which generates most gradient coding schemes.
  arXiv  Detail & Related papers  (2022-06-06T09:25:40Z)
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm [52.77024349608834]
  We propose a quantum algorithm for solving nonhomogeneous linear partial differential equations of the form $Apsi(textbfr)=f(textbfr)$. These achievements enable easier experimental implementation of the quantum algorithm based on nowadays technology.
  arXiv  Detail & Related papers  (2022-05-11T14:29:39Z)
• Efficient Floating Point Arithmetic for Quantum Computers [1.189955933770711]
  One of the major promises of quantum computing is the realization of SIMD (single instruction - multiple data) operations using the phenomenon of superposition. We introduce the formalism of encoding so called semi-booleans, which allows convenient generation of unsigned integer arithmetic quantum circuits. We extend this type of evaluation with additional features, such as ancilla-free in-place multiplication and integer coefficient evaluation.
  arXiv  Detail & Related papers  (2021-12-20T14:00:36Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  We show that a modified greedy algorithm can achieve an approximation factor of $0.305$. We derive a data-dependent upper bound on the optimum. It can also be used to significantly improve the efficiency of such algorithms as branch and bound.
  arXiv  Detail & Related papers  (2020-08-12T15:40:21Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
  arXiv  Detail & Related papers  (2020-04-16T16:12:10Z)

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.