論文の概要: Optimal Marginal Mixing for Transvection-Based Trapdoored Matrices over Large Fields

• arxiv url: http://arxiv.org/abs/2611.05573v1
• Date: Tue, 03 Nov 2026 20:05:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 03:25:57.836649
• Title: Optimal Marginal Mixing for Transvection-Based Trapdoored Matrices over Large Fields
• Title（参考訳）: 経静脈的トリップドアマトリクスの大規模領域における最適マージナルミキシング
• Abstract要約: emphTrapdoored matricesは、高速な行列ベクトル乗算アルゴリズムシークレットキーを持つ擬似ランダム行列である。 非空集合 (mathcalSsubseteq [n]times[n]) がテレビからの距離内にある場合の最悪の時間は (mathcalS|+nlog(n/varepsilon) であることを示す。 我々は(mathrmSL_n(mathrmSL_n(math))上の高効率、高並列化可能、および普遍的なトラップドア行列を示す。
• 参考スコア（独自算出の注目度）: 9.749560288448114
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: \emph{Trapdoored matrices} are pseudorandom matrices admitting a fast matrix-vector multiplication algorithm given the secret key. We study a candidate family of such matrices: matrices generated by short random \emph{transvection walks} on \(\mathrm{SL}_n(\mathbb{F}_q)\), whose steps are given by adding a random multiple of a random row of the current state to another. We show that the worst-case time for any nonempty set \(\mathcal{S}\subseteq [n]\times[n]\) of matrix entries to come within TV distance \(\varepsilon\leq \frac{1}{4}\) of its stationary marginal under this walk is \(Θ(|\mathcal{S}|+n\log(n/\varepsilon))\), uniformly over all \(\mathcal{S}\) and \(q\geq Q_\mathrm{all}(n)\). This is asymptotically optimal, and resolves open questions about the mixing times of transvection walks. We derive concrete upper and lower bounds for \(n\geq 256\). Surprisingly, our bounds also hold conditioned on the row-pair structure of the walk, except on a fraction at most \(\varepsilon\) of such structures. This implies that these walks may be pseudorandom even after conditioning on the row-pair structure, and therefore that trapdoored matrices built with these walks may be universal. Assuming the conjectured structure-conditioned pseudorandomness of short walks, we exhibit highly efficient, highly parallelizable, and universal trapdoored matrices over \(\mathrm{SL}_n(\mathbb{F}_q)\), \(\mathrm{GL}_n(\mathbb{F}_q)\), and \(\mathbb{F}_q^{n\times n}\). The families over \(\mathrm{SL}_n(\mathbb{F}_q)\) and \(\mathrm{GL}_n(\mathbb{F}_q)\) admit equally efficient trapdoors for their inverses, making them the first to do so for finite-field trapdoored matrices. We discuss attacks, analyzing one in detail, and lay out directions for further investigation.
• Abstract（参考訳）: \emph{Trapdoored matrice} は秘密鍵が与えられた高速行列ベクトル乗算アルゴリズムを許容する擬似ランダム行列である。 このような行列の候補族について検討する: 短いランダムな \emph{transvection walk} によって生成される行列を \(\mathrm{SL}_n(\mathbb{F}_q)\) 上で、そのステップは現在の状態のランダムな行のランダムな倍数を加えて与えられる。 行列成分の任意の空でない集合 \(\mathcal{S}\subseteq [n]\times[n]\) に対する最悪のケース時間は、テレビ距離 \(\varepsilon\leq \frac{1}{4}\) において、このウォークの下での静止辺辺は \(\mathcal{S}|+n\log(n/\varepsilon))\ となり、すべての \(\mathcal{S}\) と \(q\geq Q_\mathrm{all}(n)\) を均一に上回る。 これは漸近的に最適であり、横断歩行の混合時間に関するオープンな疑問を解決する。 我々は、(n\geq 256\) に対して具体的な上界と下界を導出する。 驚いたことに、我々の境界は、そのような構造のほとんどの \(\varepsilon\) における分数を除いて、ウォークの行ペア構造に条件付きである。 これは、これらのウォークは、ローペア構造を条件付けした後でも疑似ランダムである可能性があり、したがってこれらのウォークで構築されたトラップドア行列は普遍的である可能性があることを意味する。 ショートウォークの予測された構造条件の擬ランダム性を仮定すると、(\mathrm{SL}_n(\mathbb{F}_q)\), \(\mathrm{GL}_n(\mathbb{F}_q)\), \(\mathbb{F}_q^{n\times n}\) 上の非常に効率的で、高い並列化が可能で、普遍的なトラップドア行列を示す。 \(\mathrm{SL}_n(\mathbb{F}_q)\) および \(\mathrm{GL}_n(\mathbb{F}_q)\) 上の族は、その逆に対して等しく効率的なトラップドアを認め、有限体トラップドア行列に対してそのようなことを初めて行う。 我々は攻撃について議論し、詳細に分析し、さらなる調査の方向性を定めている。

関連論文リスト

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  行列連鎖乗法は、科学計算、機械学習、グラフ解析における問題である。 我々は、$K$行列の$mathcalW$を回路深さの量子状態にエンコードする量子サブルーチンであるemphTwo-Tower Matrixを提案する。
  論文  参考訳（メタデータ） (2026-07-14T18:42:40Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Highway to Hull: An Algorithm for Solving the General Matrix Code Equivalence Problem [4.450536872346658]
  本稿では,一般の場合の行列符号等価問題を解く新しいアルゴリズムを提案する。 我々のアルゴリズムは、ナラヤナンのエフェットal.と同じ時間複雑さを達成できるが、空間の複雑さは低い。
  論文  参考訳（メタデータ） (2025-04-01T22:39:31Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Structured Semidefinite Programming for Recovering Structured Preconditioners [41.28701750733703]
  正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。 我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
  論文  参考訳（メタデータ） (2023-10-27T16:54:29Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• On Fast Johnson-Lindernstrauss Embeddings of Compact Submanifolds of $\mathbb{R}^N$ with Boundary [0.4125187280299246]
  mathbbRm × N$ のランダム行列 $A がバイリプシッツ函数 $A: MathcalM rightarrow mathbbRm$ とビリプシッツ定数が 1 に近い確率を考える。 我々は、$mathbbRN$ の十分低次元部分多様体を埋め込むための、高度に構造化された分布の新しいクラスを示す。
  論文  参考訳（メタデータ） (2021-10-08T15:27:52Z)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
  論文  参考訳（メタデータ） (2021-06-27T17:25:24Z)
• Algebraic and geometric structures inside the Birkhoff polytope [0.0]
  Birkhoff polytope $mathcalB_d$ は位数 $d$ のすべての双確率行列からなる。 我々は、$mathcalL_d$ と $mathcalF_d$ が平面行列に対して星型であることを証明する。
  論文  参考訳（メタデータ） (2021-01-27T09:51:24Z)

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

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