論文の概要: A Linear-Time Algorithm for the Closest Vector Problem of Triangular Lattices

• arxiv url: http://arxiv.org/abs/2412.06091v1
• Date: Sun, 08 Dec 2024 22:47:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-10 14:52:15.270252
• Title: A Linear-Time Algorithm for the Closest Vector Problem of Triangular Lattices
• Title（参考訳）: 三角格子の閉ベクトル問題に対する線形時間アルゴリズム
• Authors: Kenta Takahashi, Wataru Nakamura,
• Abstract要約: 従来のCVPアルゴリズムでは$O(n log n)$-timeを必要とするのに対し、CVPアルゴリズムは$O(n log n)$-timeである。 さらに改良を行い,$O(n)$-timeアルゴリズムを構築した。
• 参考スコア（独自算出の注目度）: 1.62060928868899
• License:
• Abstract: Fuzzy Extractor (FE) and Fuzzy Signature (FS) are useful schemes for generating cryptographic keys from fuzzy data such as biometric features. Several techniques have been proposed to implement FE and FS for fuzzy data in an Euclidean space, such as facial feature vectors, that use triangular lattice-based error correction. In these techniques, solving the closest vector problem (CVP) in a high dimensional (e.g., 128--512 dim.) lattice is required at the time of key reproduction or signing. However, solving CVP becomes computationally hard as the dimension $n$ increases. In this paper, we first propose a CVP algorithm in triangular lattices with $O(n \log n)$-time whereas the conventional one requires $O(n^2)$-time. Then we further improve it and construct an $O(n)$-time algorithm.
• Abstract（参考訳）: Fuzzy Extractor (FE) と Fuzzy Signature (FS) は、バイオメトリックスのようなファジィデータから暗号鍵を生成するための有用なスキームである。 顔の特徴ベクトルのようなユークリッド空間におけるファジィデータに対して、三角形格子に基づく誤り訂正を用いたFEとFSを実装するために、いくつかの手法が提案されている。 これらの手法では、鍵再生や署名の際には、高次元(例えば、18〜512桁)格子において最も近いベクトル問題(CVP)を解く必要がある。 しかし、CVP の解法は、次元が $n$ になるにつれて計算的に困難になる。 本稿では,まず,O(n \log n)$-time の三角形格子を用いた CVP アルゴリズムを提案し,従来のアルゴリズムでは$O(n^2)$-time が必要であった。 さらに改良を行い、$O(n)$-timeアルゴリズムを構築する。

関連論文リスト

• An Attack on $p$-adic Lattice Public-key Cryptosystems and Signature Schemes [3.444630356331766]
  本稿では,局所フィールドにおけるLVPアルゴリズムの改良について述べる。 このアルゴリズムを用いて上記のスキームを攻撃し、任意のメッセージをフォージし、暗号文を復号化できるようにします。 これらのスキームは壊れているが、この研究は、$p$-adic 格子が暗号プリミティブの構築に適さないという意味ではない。
  論文  参考訳（メタデータ） (2024-09-13T12:31:57Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Finding dense sub-lattices as low-energy states of a Hamiltonian [1.2183430883527995]
  格子ベースの暗号は、量子後暗号の最も顕著な候補の1つである。 最短ベクトル問題(SVP)は、与えられた格子の中で最短の非ゼロベクトルを見つけることである。 我々は、与えられた格子の最も密度の高い$K$-Densest Sub-lattice(K$-DSP)を求めるために、$K$-Densest Sub-lattice Problem(K$-DSP)として知られるSVPの自然な一般化を研究する。
  論文  参考訳（メタデータ） (2023-09-28T08:48:38Z)
• 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)
• Reduced Contraction Costs of Corner-Transfer Methods for PEPS [0.0]
  無限に投影された絡み合ったペア状態の収縮を抑えるための最優先計算コストを削減できる近似法を提案する。 計算コストの改善により、大きな結合次元の計算が可能となり、そのポテンシャルを拡大して課題を解決することができる。
  論文  参考訳（メタデータ） (2023-06-14T02:54:12Z)
• A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning [9.628032156001073]
  立方正則化を取り入れた2つのポリシーニュートンアルゴリズムを提案する。 どちらのアルゴリズムも確率比法を用いて値関数の勾配とヘシアンを推定する。 特に、我々のアルゴリズムのサンプル複雑さが$epsilon$-SOSPを見つけるのに$O(epsilon-3.5)$であり、これは最先端のサンプル複雑性の$O(epsilon-4.5)$よりも改善されている。
  論文  参考訳（メタデータ） (2023-04-21T13:43:06Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition [0.0]
  確率分布からサンプリングするLangevin型アルゴリズムの代用として,Stein Variational Gradient Descent (SVGD) が重要である。 既存のランゲヴィン型アルゴリズムとSVGDの理論では、ポテンシャル関数 $V$ はしばしば $L$-smooth と仮定される。
  論文  参考訳（メタデータ） (2022-06-01T14:08:35Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

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

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