論文の概要: On Compression Functions over Groups with Applications to Homomorphic Encryption

• arxiv url: http://arxiv.org/abs/2208.02468v2
• Date: Thu, 03 Jul 2025 03:39:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-04 15:37:12.274138
• Title: On Compression Functions over Groups with Applications to Homomorphic Encryption
• Title（参考訳）: ホモモルフィック暗号化への応用をもつ群上の圧縮関数について
• Authors: Koji Nuida,
• Abstract要約: ホモモルフィック暗号化(FHE)は、エンティティが暗号化されたデータを復号することなく任意の計算を行うことを可能にする。 そのような函数が任意の可解群$G$上に存在しないことを示す。 また、最も短い式を持つ交互群 $G = A_5$ 上のそのような関数も構成する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 完全同型暗号化(FHE)は、エンティティが暗号文を復号することなく暗号化データ上で任意の計算を行うことを可能にする。 FHE スキームを構成するための群論的アプローチでは、与えられた有限群 $G$ 上の群演算によって実装されたある種の "圧縮" 関数 $F(x)$ を使い、$F(1) = 1$ と $F(\sigma) = F(\sigma^2) = \sigma$ を満たす。 以前の研究は、対称群 $G = S_5$ 上のそのような函数のただのヒューリスティックなアプローチによる例を与えた。 本稿では,様々なグループにまたがるそのような機能の可能性について,系統的に検討する。 そのような函数が任意の可解群$G$(例えば、アーベル群やより小さな対称群$S_n$と$n \leq 4$)の上に存在しないことを示す。 また、最も短い式を持つ交互群 $G = A_5$ 上のそのような関数も構成する。 さらに、この新しい関数を用いることで、FHE スキームの構成を$A_5$ 群上の同型暗号化スキームの構成に還元する。

関連論文リスト

• Block Encodings of Discrete Subgroups on Quantum Computer [23.493000556496376]
  本稿では,離散部分群を量子コンピュータ上の量子ビットにマッピングするブロック符号化手法を提案する。 インバージョンゲート、グループ乗算ゲート、トレースゲート、グループフーリエゲートといったプリミティブゲートの構築について詳述する。 $mathbbBT$と$mathbbBI$の逆ゲートは、$textttwang$量子コンピュータ上で、それぞれ40+5_-4%$と4+5_-3%$と見積もられている。
  論文  参考訳（メタデータ） (2024-05-21T16:00:04Z)
• Synthesis and Arithmetic of Single Qutrit Circuits [0.8192907805418581]
  本稿では,Clifford$+D$サイクロトミックゲート集合上の単語からなるクォート回路について検討する。 このフレームワークは、任意の素数の四重項に拡張するクリフォード$+D$の四重項ゲート合成を定式化するために開発された。
  論文  参考訳（メタデータ） (2023-11-15T04:50:41Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。 この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
  論文  参考訳（メタデータ） (2023-03-06T17:54:33Z)
• Optimal universal quantum circuits for unitary complex conjugation [1.6492989697868894]
  この研究は、$U_d$のコール数$k$を複素共役$barU_d$に変換するための最適量子回路を示す。 我々の回路は並列実装を認めており、$k$と$d$の平均忠実度が$leftlangleFrightrangle =frack+1d(d-k)$に対して最適であることが証明されている。
  論文  参考訳（メタデータ） (2022-05-31T20:43:29Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。