論文の概要: The planted tensor problem over finite fields: algorithms and cryptography

• arxiv url: http://arxiv.org/abs/2609.31256v1
• Date: Fri, 25 Sep 2026 13:32:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 18:27:51.409355
• Title: The planted tensor problem over finite fields: algorithms and cryptography
• Title（参考訳）: 有限体上の植込みテンソル問題:アルゴリズムと暗号
• Abstract要約: ランダムテンソルに対する植込み斜め問題に着想を得て、ランダムテンソルに対する植込み完全等方空間問題を導入する。 この問題は,非可換ランク問題における最近の進歩を活用して,$dgeq n/2$に対する平均ケースタイムアルゴリズムを適用可能であることを示す。 我々は、ある定数$Cgeq 3$を持つ$d=lceil n/Crceil$ に対する完全等方的空間問題は指数関数的に難しいと推測する。
• 参考スコア（独自算出の注目度）: 7.009214476635338
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Inspired by the planted clique problem for random graphs, we introduce the planted totally-isotropic space problem for random tensors as follows. Let $U\cong \mathbb{F}_q^n$ and $W\cong \mathbb{F}_q^m$ be finite-dimensional vector spaces over a finite field $\mathbb{F}_q$. Given $d\in \mathbb{N}$, choose a random \(d\)-dimensional subspace \(V\leq U\), and construct a random alternating bilinear map $φ:U\times U\to W$ subject to the constraint \(φ(V,V)=0\). Such a $V$ is known as a totally-isotropic space of $φ$, and the goal is to recover $V$. Building on the recent probabilistic analysis of random tensors (Pham--Qiao--Wigderson--Wigderson, \emph{in progress}), we initiate the study of the algorithmic hardness of this problem. Setting $m=\lceil n/\log n\rceil$, we show that this problem admits an average-case polynomial-time algorithm for $d\geq n/2$, by leveraging recent advances on the non-commutative rank problem. We also show that this problem admits a $q^{O(n\log n)}$-time algorithm. We carry out algorithmic experiments using polynomial-system solving. From these results, we conjecture that the planted totally-isotropic space problem for $d=\lceil n/C\rceil$ with some constant $C\geq 3$ is exponentially hard. Based on this evidence of computational hardness, we explore cryptographic applications of the planted totally-isotropic space problem and related planted tensor problems. We present private simultaneous messages and secret sharing protocols based on planted tensor problems, following the protocols based on planted subgraphs in (Abram--Beimel--Ishai--Kushilevitz--Narayanan, \emph{TCC}'23). At the same security level, the public information size of protocols based on planted subgraphs is (moderately) exponential in that of protocols based on planted tensors, while the communication costs of these protocols are polynomially related.
• Abstract（参考訳）: ランダムグラフに対する植込み斜め問題に着想を得て、ランダムテンソルに対する植込み完全等方空間問題を導入する。 U\cong \mathbb{F}_q^n$ と $W\cong \mathbb{F}_q^m$ を有限体 $\mathbb{F}_q$ 上の有限次元ベクトル空間とする。 d\in \mathbb{N}$ が与えられたとき、ランダム \(d\)-次元部分空間 \(V\leq U\) を選択し、制約 \(φ(V,V)=0\ に従うランダム交互双線型写像 $φ:U\times U\to W$ を構成する。 そのような$V$は$φ$の完全等方空間として知られ、その目標は$V$を回復することである。 ランダムテンソル(Pham--Qiao--Wigderson--Wigderson, \emph{in progress})の最近の確率論的解析に基づいて、この問題のアルゴリズム的硬さの研究を開始する。 m=\lceil n/\log n\rceil$ を設定すると、この問題は非可換ランク問題に対する最近の進歩を活用して、$d\geq n/2$ の平均ケース多項式時間アルゴリズムを許容することを示す。 また、この問題には$q^{O(n\log n)}$-timeアルゴリズムがあることも示している。 多項式系解法を用いてアルゴリズム実験を行う。 これらの結果から、ある定数$C\geq 3$を持つ$d=\lceil n/C\rceil$に対する完全等方空間問題は指数関数的に難しいと推測する。 計算硬度のこの証拠に基づき, 植付された完全等方性空間問題と関連する植付テンソル問題の暗号的応用について検討する。 Abram--Beimel--Ishai--Kushilevitz--Narayanan, \emph{TCC}'23。 同じセキュリティレベルでは、植字された部分グラフに基づくプロトコルの公開情報サイズは、植字されたテンソルに基づくプロトコルのそれに対して指数関数的であるが、これらのプロトコルの通信コストは多項式的に関連している。

関連論文リスト

• Lattice Based Crypto breaks in a Superposition of Spacetimes [3.125009120066803]
  量子重力理論において仮定された時空の重ね合わせの計算的含意について検討する。 格子ベースの暗号スキームのセキュリティは、時空の重畳に基づく計算モデルで妥協される。
  論文  参考訳（メタデータ） (2025-03-27T11:45:13Z)
• Detecting Arbitrary Planted Subgraphs in Random Graphs [7.320365821066746]
  本稿では,ErdHos-R'enyi乱数グラフ$mathcalG(n, q_n)$における仮設植木部分グラフ$Gamma = Gamma_n$の検出について検討する。 エッジ確率が$p_n$と$q_n$が固定された高密度な状態では、Gamma$を検出するための情報理論および計算しきい値が強く特徴付けられる。
  論文  参考訳（メタデータ） (2025-03-24T18:54:43Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。 我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-10-05T09:39:51Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)

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

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