論文の概要: Bootstrapping as a Morphism: An Arithmetic Geometry Approach to Asymptotically Faster Homomorphic Encryption
- arxiv url: http://arxiv.org/abs/2510.02365v1
- Date: Mon, 29 Sep 2025 03:39:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-06 16:35:52.046327
- Title: Bootstrapping as a Morphism: An Arithmetic Geometry Approach to Asymptotically Faster Homomorphic Encryption
- Title（参考訳）: 形態素としてのブートストラップ : 漸近的に高速な同型暗号化への算術的幾何学的アプローチ
- Authors: Dongfang Zhao,
- Abstract要約: 本稿では,従来の回路評価モデルを完全にバイパスするブートストラップ手法を提案する。
直射射影としてブートストラップ操作を再構成するために,現代の算術幾何学のツールを適用した。
我々の研究は、$O(d cdot textpoly(log q))$、$d$が環次元、$q$が暗号文である完全かつ確実に正しいブートストラップアルゴリズムである。
- 参考スコア（独自算出の注目度）: 0.9179857807576733
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Fully Homomorphic Encryption (FHE) provides a powerful paradigm for secure computation, but its practical adoption is severely hindered by the prohibitive computational cost of its bootstrapping procedure. The complexity of all current bootstrapping methods is fundamentally tied to the multiplicative depth of the decryption circuit, denoted $L_{dec}$, making it the primary performance bottleneck. This paper introduces a new approach to bootstrapping that completely bypasses the traditional circuit evaluation model. We apply the tools of modern arithmetic geometry to reframe the bootstrapping operation as a direct geometric projection. Our framework models the space of ciphertexts as an affine scheme and rigorously defines the loci of decryptable and fresh ciphertexts as distinct closed subschemes. The bootstrapping transformation is then realized as a morphism between these two spaces. Computationally, this projection is equivalent to solving a specific Closest Vector Problem (CVP) instance on a highly structured ideal lattice, which we show can be done efficiently using a technique we call algebraic folding. The primary result of our work is a complete and provably correct bootstrapping algorithm with a computational complexity of $O(d \cdot \text{poly}(\log q))$, where $d$ is the ring dimension and $q$ is the ciphertext modulus. The significance of this result lies in the complete elimination of the factor $L_{dec}$ from the complexity, representing a fundamental asymptotic improvement over the state of the art. This geometric perspective offers a new and promising pathway toward achieving truly practical and high-performance FHE.
- Abstract（参考訳）: FHE(Fully Homomorphic Encryption)は、セキュアな計算のための強力なパラダイムを提供するが、ブートストラッピング手順の禁止された計算コストによって、その実践的採用が著しく妨げられている。
現在のブートストラップ法の複雑さは、復号回路の乗算深さ($L_{dec}$)と基本的に結びついており、主な性能ボトルネックとなっている。
本稿では,従来の回路評価モデルを完全にバイパスするブートストラップ手法を提案する。
直射射影としてブートストラップ操作を再構成するために,現代の算術幾何学のツールを適用した。
我々のフレームワークは、アフィンスキームとして暗号文の空間をモデル化し、復号可能な新しい暗号文のロシを、異なる閉じたサブスキームとして厳密に定義する。
ブートストラップ変換は、これらの2つの空間の間の射として実現される。
計算学的には、この射影は高度に構造化された理想格子上で特定の閉ベクトル問題(CVP)を解くのと等価であり、代数的折り畳みと呼ばれる手法を用いて効率的に行うことができる。
我々の研究の主な成果は、計算複雑性が$O(d \cdot \text{poly}(\log q))$, $d$が環次元、$q$が暗号文係数である完全かつ証明可能なブートストラップアルゴリズムである。
この結果の意義は、複雑さから$L_{dec}$の因子を完全に排除することであり、最先端技術に対する基本的な漸近的改善を表している。
この幾何学的視点は、真に実用的で高性能なFHEを達成するための、新しくて有望な経路を提供する。
関連論文リスト
- Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms [22.546453748805025]
我々は、計算コストのかかる削減ステップを特定し、排除するTransformerベースのオラクルを設計し、訓練する。
ベースアルゴリズムと比較して, 最大3.5倍の高速化率を実現した。
我々の学習アプローチは、データ効率が高く、安定であり、従来の計算機代数アルゴリズムや記号計算の実践的な拡張である。
論文 参考訳（メタデータ） (2025-05-29T17:35:25Z) - Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited [4.843809993270313]
2次元格子における最短ベクトル問題(SVP)の効率的な解法は、暗号や計算幾何学において実際的な重要性を持つ。
我々は、ユークリッドアルゴリズムを次元にわたって戦略的に適用する効率的な適応格子削減アルゴリズム textbfCrossEuc を開発した。
textbfHVecを反復的に呼び出すことによって、最適化されたアルゴリズム textbfHVecSBP は、ビット長$n$の任意の入力ベースに対して$O(log n M(n) )$ time の還元基底を得る。
論文 参考訳（メタデータ） (2025-04-17T13:50:51Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Object Representations as Fixed Points: Training Iterative Refinement
Algorithms with Implicit Differentiation [88.14365009076907]
反復的洗練は表現学習に有用なパラダイムである。
トレーニングの安定性とトラクタビリティを向上させる暗黙の差別化アプローチを開発する。
論文 参考訳（メタデータ） (2022-07-02T10:00:35Z) - Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。
本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
論文 参考訳（メタデータ） (2021-07-05T00:51:02Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。
提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
論文 参考訳（メタデータ） (2020-03-30T15:37:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。