On Compression Functions over Groups with Applications to Homomorphic Encryption

• URL: http://arxiv.org/abs/2208.02468v2
• Date: Thu, 03 Jul 2025 03:39:00 GMT
• Title: On Compression Functions over Groups with Applications to Homomorphic Encryption
• Authors: Koji Nuida,
• Abstract summary: Homomorphic encryption (FHE) enables an entity to perform arbitrary computation without decrypting encrypted data.<n>We show that such a function does not exist over any solvable group $G$.<n>We also construct such a function over the alternating group $G = A_5$ that has a shortest possible expression.
• Score: 0.43512163406552007
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fully homomorphic encryption (FHE) enables an entity to perform arbitrary computation on encrypted data without decrypting the ciphertexts. An ongoing group-theoretical approach to construct an FHE scheme uses a certain "compression" function $F(x)$ implemented by group operations on a given finite group $G$, which satisfies that $F(1) = 1$ and $F(\sigma) = F(\sigma^2) = \sigma$ where $\sigma \in G$ is some element of order $3$. The previous work gave an example of such a function over the symmetric group $G = S_5$ by just a heuristic approach. In this paper, we systematically study the possibilities of such a function over various groups. We show that such a function does not exist over any solvable group $G$ (such as an Abelian group and a smaller symmetric group $S_n$ with $n \leq 4$). We also construct such a function over the alternating group $G = A_5$ that has a shortest possible expression. Moreover, by using this new function, we give a reduction of a construction of an FHE scheme to a construction of a homomorphic encryption scheme over the group $A_5$, which is more efficient than the previously known reductions.

Related papers

• Group Representational Position Encoding [66.33026480082025]
  We present GRAPE, a unified framework for positional encoding based on group actions.<n>Two families of mechanisms: (i) multiplicative rotations (Multiplicative GRAPE) in $mathrmSO(d)$ and (ii) additive logit biases (Additive GRAPE) arising from unipotent actions in the general linear group $mathrmGL$.
  arXiv  Detail & Related papers  (2025-12-08T18:39:13Z)
• Probabilistic Bounds on the Number of Elements to Generate Finite Nilpotent Groups and Their Applications [4.250782756734906]
  We prove that $varphi_k(G) ge 1 - $ if $k ge operatornamerank(G) + lceil log(2/) rceil$ (a bound based on the group rank) or if $k ge operatornamelen(G) + lceil log (1/) rceil$ (a bound based on the group chain length)
  arXiv  Detail & Related papers  (2025-11-23T12:30:46Z)
• An Efficient Computational Framework for Discrete Fuzzy Numbers Based on Total Orders [41.99844472131922]
  We introduce algorithms that exploit the structure of total (admissible) orders to compute the $textitpos$ function.<n>The proposed approach achieves a complexity of $mathcalO(n2 m log n)$, which is quadratic in the size of the underlying chain.<n>The results demonstrate that this formulation substantially reduces computational cost.
  arXiv  Detail & Related papers  (2025-11-21T09:35:07Z)
• A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group [0.0]
  We propose a symmetric-key cryptosystem whose linear action takes place instead in the Burnside ring $A(G)$ of a compact Lie group $G$.<n>Messages of arbitrary finite length are encoded as finitely supported elements of $A(G)$ and encrypted via the Burnside product with $k$.<n>We show that any finite set of observations constrains the action only on a finite-rank submodule $W_Lsubset A(O(2))$, and we show information-theoretic non-identifiability of the key from such data.
  arXiv  Detail & Related papers  (2025-10-13T01:57:22Z)
• Approximate Degrees of Multisymmetric Properties with Application to Quantum Claw Detection [0.0]
  The optimal quantum complexity of the problem is known to be $Omegaleft(sqrtG+(FG)1/6M1/6right)$ for input functions $fcolon [F]to Z$ and $gcolon [G]to Z$. The current paper proves the lower bound holds even for every smaller range $Z$ with $|Z|=Omega(FG)$.
  arXiv  Detail & Related papers  (2024-10-03T06:32:34Z)
• Block Encodings of Discrete Subgroups on Quantum Computer [23.493000556496376]
  We introduce a block encoding method for mapping discrete subgroups to qubits on a quantum computer. We detail the construction of primitive gates -- the inversion gate, the group multiplication gate, the trace gate, and the group Fourier gate. The inversion gates for $mathbbBT$ and $mathbbBI$ are benchmarked on the $textttwang$ quantum computer with estimated fidelities of $40+5_-4%$ and $4+5_-3%$ respectively.
  arXiv  Detail & Related papers  (2024-05-21T16:00:04Z)
• Polyadic sigma matrices [0.0]
  We generalize $sigma$-matrices to higher arities using the polyadization procedure proposed by the author. The presentation of $n$-ary $SUleft( 2right) $ in terms of full $Sigma$-matrices is done using the Hadamard product.
  arXiv  Detail & Related papers  (2024-03-28T12:19:46Z)
• Synthesis and Arithmetic of Single Qutrit Circuits [0.8192907805418581]
  We study qutrit circuits consisting of words over the Clifford$+D$ cyclotomic gate set.<n>The framework developed to formulate qutrit gate synthesis for Clifford$+D$ extends to qudits of arbitrary prime power.
  arXiv  Detail & Related papers  (2023-11-15T04:50:41Z)
• Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits [0.8411424745913132]
  We show that when $n$ is a power of 2, a multiqubit unitary matrix $U$ can be exactly represented by a circuit over $mathcalG_n$. We moreover show that $log(n)-2$ ancillas are always sufficient to construct a circuit for $U$.
  arXiv  Detail & Related papers  (2023-11-13T20:46:51Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  We give a statistical characterization of the $gamma$-regret for arbitrary structured bandit problems. The $gamma$-regret emerges in structured bandit problems over a function class $mathcalF$ where finding an exact optimum of $f in mathcalF$ is intractable.
  arXiv  Detail & Related papers  (2023-03-06T17:54:33Z)
• Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs [66.47284608209692]
  We propose an algorithm for general acyclic WFSAs which runs in $Oleft(|E| + s |Sigma| |Q| T_textmax log|Sigma|right)$. When the failure transition topology satisfies a condition exemplified by CRFs, the $T_textmax$ factor can be dropped. In the latter case (ring-weighted acyclic WFSAs), we also give an alternative algorithm complexity with $style Oleft(|E| + |Sigma| |
  arXiv  Detail & Related papers  (2023-01-17T13:15:44Z)
• Optimal universal quantum circuits for unitary complex conjugation [1.6492989697868894]
  This work presents optimal quantum circuits for transforming a number $k$ of calls of $U_d$ into its complex conjugate $barU_d$. Our circuits admit a parallel implementation and are proven to be optimal for any $k$ and $d$ with an average fidelity of $leftlangleFrightrangle =frack+1d(d-k)$.
  arXiv  Detail & Related papers  (2022-05-31T20:43:29Z)
• On Submodular Contextual Bandits [92.45432756301231]
  We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function. We show that our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy.
  arXiv  Detail & Related papers  (2021-12-03T21:42:33Z)
• Submodular + Concave [53.208470310734825]
  It has been well established that first order optimization methods can converge to the maximal objective value of concave functions. In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$. This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
  arXiv  Detail & Related papers  (2021-06-09T01:59:55Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

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.