論文の概要: Low-Complexity Integer Divider Architecture for Homomorphic Encryption
- arxiv url: http://arxiv.org/abs/2401.11064v1
- Date: Fri, 19 Jan 2024 23:53:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 08:36:55.332859
- Title: Low-Complexity Integer Divider Architecture for Homomorphic Encryption
- Title(参考訳): 均質暗号化のための低複雑さ整数ディバイダアーキテクチャ
- Authors: Sajjad Akherati, Jiaxuan Cai, Xinmiao Zhang,
- Abstract要約: ホモモルフィック暗号化(HE)は、計算を直接暗号文で行うことができ、プライバシ保護のクラウドコンピューティングを可能にする。
余剰かつ活発な数学的証明を計算するアルゴリズムが提案されている。
- 参考スコア(独自算出の注目度): 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$.
- Abstract(参考訳): ホモモルフィック暗号化(HE)は、計算を直接暗号文で行うことができ、プライバシ保護のクラウドコンピューティングを可能にする。
HE に関係する多項式の係数に関する計算は常にモジュラー化され、商を利用することで、暗号文の乗算の全体的な複雑さを低減できる。
これまでの設計では、配当がモジュラーの整数倍であり、モジュラーが$u<w/2$である2^w-2^u\pm1$の形式である場合を考える。
本稿では、この除算はより大きい$u$に対して一般化され、モジュラーの整数倍ではない配当となる。
余剰かつ活発な数学的証明を計算するアルゴリズムが提案されている。
さらに,提案アルゴリズムの実装のために,効率的なハードウェアアーキテクチャを開発した。
因子の逆数を利用する別の除算法と比較すると、$w=32$ の場合、提案設計は少なくとも9%のレイテンシと 79 % の領域削減を実現し、$u$ の75% の値が得られる。
関連論文リスト
- A new lightweight additive homomorphic encryption algorithm [0.0]
本稿では、同じ暗号鍵と復号鍵を持つ軽量な加法的同型アルゴリズムについて述べる。
これにより、モジュラー指数からモジュラー乗算への暗号化と復号化の計算コストが削減される。
論文 参考訳(メタデータ) (2023-12-12T05:12:20Z) - Practical Parallel Algorithms for Non-Monotone Submodular Maximization [20.13836086815112]
Submodularは、人工知能の分野における様々な分野に広く応用されている。
部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。
証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
論文 参考訳(メタデータ) (2023-08-21T11:48:34Z) - Fast algorithms for k-submodular maximization subject to a matroid
constraint [10.270420338235237]
マトロイド制約の下では、Threshold-Decreasing Algorithmを用いて$k$-submodular関数を最大化する。
我々は$k$-submodular関数に対して$(frac12 - epsilon)$-approximationアルゴリズムを与える。
論文 参考訳(メタデータ) (2023-07-26T07:08:03Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint [16.02833173359407]
この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
論文 参考訳(メタデータ) (2023-05-17T15:27:33Z) - Optimization-based Block Coordinate Gradient Coding for Mitigating
Partial Stragglers in Distributed Learning [58.91954425047425]
本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。
L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
論文 参考訳(メタデータ) (2022-06-06T09:25:40Z) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。
これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
論文 参考訳(メタデータ) (2022-05-11T14:29:39Z) - Efficient Floating Point Arithmetic for Quantum Computers [1.189955933770711]
量子コンピューティングの大きな約束の1つは、重ね合わせ現象を用いたSIMD(単一命令 - 複数のデータ)演算の実現である。
我々は、符号なし整数量子回路を便利に生成できる半ブールと呼ばれる符号化形式を導入している。
我々は、このタイプの評価を、アンシラのないインプレース乗算や整数係数評価などの追加機能で拡張する。
論文 参考訳(メタデータ) (2021-12-20T14:00:36Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳(メタデータ) (2020-08-12T15:40:21Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。
学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文 参考訳(メタデータ) (2020-04-16T16:12:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。