論文の概要: Large-Plaintext Functional Bootstrapping in FHE with Small Bootstrapping Keys
- arxiv url: http://arxiv.org/abs/2310.12441v1
- Date: Thu, 19 Oct 2023 03:30:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-19 02:03:55.753190
- Title: Large-Plaintext Functional Bootstrapping in FHE with Small Bootstrapping Keys
- Title(参考訳): 小型ブートストラップキーを用いたFHEにおける大文字機能ブートストラップ
- Authors: Dengfa Liu, Hongbo Li,
- Abstract要約: 機能的ブートストラップは完全同型暗号化(FHE)のコア技術である
本稿では,ベクトル内の任意の関数のルックアップテーブルを符号化し,その係数がより多くのデータを保持できることを示す。
新しいアルゴリズムは、キーサイズが小さく、キースイッチングのキーサイズが小さいことで、キーサイズが大幅に改善され、実行時のコストが一定に向上する。
- 参考スコア(独自算出の注目度): 1.6319731389952283
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Functional bootstrapping is a core technique in Fully Homomorphic Encryption (FHE). For large plaintext, to evaluate a general function homomorphically over a ciphertext, in the FHEW/TFHE approach, since the function in look-up table form is encoded in the coefficients of a test polynomial, the degree of the polynomial must be high enough to hold the entire table. This increases the bootstrapping time complexity and memory cost, as the size of bootstrapping keys and keyswitching keys need to be large accordingly. In this paper, we propose to encode the look-up table of any function in a polynomial vector, whose coefficients can hold more data. The corresponding representation of the additive group Zq used in the RGSW-based bootstrapping is the group of monic monomial permutation matrices, which integrates the permutation matrix representation used by Alperin-Sheriff and Peikert in 2014, and the monic monomial representation used in the FHEW/TFHE scheme. We make comprehensive investigation of the new representation, and propose a new bootstrapping algorithm based on it. The new algorithm has the prominent benefit of small bootstrapping key size and small key-switching key size, which leads to polynomial factor improvement in key size, in addition to constant factor improvement in run-time cost.
- Abstract(参考訳): 機能的ブートストラッピングは、フルホモモルフィック暗号化(FHE)のコア技術である。
大規模な平文の場合、FHEW/TFHEアプローチでは、テスト多項式の係数にルックアップテーブル形式の関数が符号化されているため、一般関数を暗号文上で同型的に評価するためには、多項式の次数はテーブル全体を保持するのに十分高くなければならない。
これによりブートストラップ時間の複雑さとメモリコストが増加し、ブートストラップキーとキースイッチングキーのサイズが大きくなる必要がある。
本稿では,係数がより多くのデータを保持する多項式ベクトルの任意の関数のルックアップテーブルを符号化する。
RGSWベースのブートストラップで用いられる加法群 Zq の対応する表現は、2014年にアルペリン・シェリフとピーカルトによって用いられた置換行列表現と、FHEW/TFHEスキームで用いられるモニック単相表現を統合するモニック単相行列群である。
本稿では,新しい表現を包括的に検討し,それに基づくブートストラップアルゴリズムを提案する。
新しいアルゴリズムは、キーサイズが小さく、キースイッチングのキーサイズが小さいことで、キーサイズが多項式的に改善され、実行時のコストが一定に向上する。
関連論文リスト
- VLWE: Variety-based Learning with Errors for Vector Encryption through Algebraic Geometry [1.3824176915623292]
格子ベースの暗号はポスト量子セキュリティの基礎である。
この研究は代数幾何学に基づく新しい構造格子問題であるバラエティ-LWE(VLWE)を導入する。
VLWEのセキュリティは、複数の独立したインスタンスに分散し、古典的および量子的攻撃に対するレジリエンスを示すことによって証明する。
論文 参考訳(メタデータ) (2025-02-11T06:04:24Z) - Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
関数の階数$f$は、単層トランスフォーマーデコーダで要求される思考の連鎖の最小値に対応することを示す。
また、ブール列における1の$k$-thの発生位置を同定する問題を解析し、$k$CoTステップが必要であることを証明した。
論文 参考訳(メタデータ) (2025-01-22T16:30:58Z) - Implementation of Entropically Secure Encryption: Securing Personal Health Data [0.704590071265998]
Entropically Secure Encryption (ESE) はOne-Time Padに短いキーで無条件のセキュリティを提供する。
バルク暗号のためのESEの実装について述べる。
論文 参考訳(メタデータ) (2024-04-04T12:07:33Z) - Simple Multigraph Convolution Networks [49.19906483875984]
既存のマルチグラフ畳み込み法では、複数のグラフ間のクロスビューの相互作用を無視するか、あるいは標準的なクロスビュー演算子によって非常に高い計算コストが生じる。
本稿では,まずエッジレベルやサブグラフレベルのトポロジを含むマルチグラフから一貫したクロスビュートポロジを抽出し,その後,生のマルチグラフと一貫したトポロジに基づいて拡張を行う,シンプルなマルチ畳み込みネットワーク(SMGCN)を提案する。
理論上、SMGCNは標準的なクロスビュー拡張ではなく、一貫した拡張のトポロジを利用して、信頼性の高いクロスビュー空間メッセージパッシングを行い、標準拡張の複雑さを効果的に低減する。
論文 参考訳(メタデータ) (2024-03-08T03:27:58Z) - QPP and HPPK: Unifying Non-Commutativity for Quantum-Secure Cryptography
with Galois Permutation Group [0.0]
我々は、対称鍵暗号のための量子置換パッド(QPP)と、鍵カプセル化機構(KEM)のための同型多項式公開鍵(HPPK)とデジタル署名(DS)の2つの新しいプリミティブを活用する。
QPPは量子セキュアな対称鍵暗号を実現し、シャノンの完全秘密を古典的および量子ネイティブなシステムにシームレスに拡張する。
NPハード問題のないHPPKは、平易な公開鍵の対称暗号化を補強する。
論文 参考訳(メタデータ) (2024-02-02T19:10:43Z) - Homomorphic Polynomial Public Key Cryptography for Quantum-secure Digital Signature [0.7864304771129751]
2022年の研究では、KuangらはMPPK暗号を導入した。
彼らはMPPKをホモモルフィックなポリノミアル公開鍵(HPPK)に拡張し、大きな隠蔽リング操作に同型暗号化を適用した。
論文 参考訳(メタデータ) (2023-11-15T13:54:23Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-30T15:57:14Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳(メタデータ) (2020-11-09T18:32:22Z) - Supervised Quantile Normalization for Low-rank Matrix Approximation [50.445371939523305]
我々は、$X$ の値と $UV$ の値を行ワイズで操作できる量子正規化演算子のパラメータを学習し、$X$ の低ランク表現の質を改善する。
本稿では,これらの手法が合成およびゲノムデータセットに適用可能であることを実証する。
論文 参考訳(メタデータ) (2020-02-08T21:06:02Z) - Invariant Feature Coding using Tensor Product Representation [75.62232699377877]
我々は,群不変特徴ベクトルが線形分類器を学習する際に十分な識別情報を含んでいることを証明した。
主成分分析やk平均クラスタリングにおいて,グループアクションを明示的に考慮する新たな特徴モデルを提案する。
論文 参考訳(メタデータ) (2019-06-05T07:15:17Z) - Post-Quantum Cryptography(PQC): Generalized ElGamal Cipher over GL(8,F251) [0.0]
ポスト量子暗号(PQC)は、攻撃に耐性のある暗号プロトコルを見つけようとする。
本稿では、一般化されたElGamal非軌道化プロトコルに基づく非対称暗号に焦点をあてる。
論文 参考訳(メタデータ) (2017-02-12T22:50:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。