論文の概要: Zeta-Transform Evaluation for Higher-Order Vanishing Key Recovery
- arxiv url: http://arxiv.org/abs/2609.26132v1
- Date: Sat, 08 Aug 2026 14:23:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-28 05:09:55.885988
- Title: Zeta-Transform Evaluation for Higher-Order Vanishing Key Recovery
- Title（参考訳）: 高次バンシングキー回復のためのゼータ変換評価
- Abstract要約: Hemmert の Classic McEliece のキー-リカバリアルゴリズムは高次消滅に基づいている。
重み付き上ゼータ変換として,$widetildevarphi_A(p)$を定義する和を列単位で評価できることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Hemmert's key-recovery algorithm for Classic McEliece is based on higher-order vanishing. It computes a basis of $\ker(\widetilde\varphi_A^{(p)})$, where $A=H'''$ is the shortened parity-check matrix used in the attack. For Classic McEliece parameters, this kernel computation is the dominant cost of the attack. We show that the sums defining $\widetilde\varphi_A^{(p)}$ can be evaluated, column by column, as weighted upper zeta transforms on the Boolean lattice. Since only selected levels of these transforms are required by $\widetilde\varphi_A^{(p)}$, restricting their evaluation to the band between level $p$ and the lowest required level yields exact evaluations of both $\widetilde\varphi_A^{(p)}$ and its transpose. Using the resulting truncated zeta-transform evaluation in the Wiedemann-based kernel computation reduces the cost of the repeated matrix--vector products without changing the overall key-recovery algorithm. The exact cost depends on the weight distribution of the non-pivot columns of $H'''$. We therefore consider two models: an all-one model, in which every relevant binary coordinate is active, and a Bernoulli$(1/2)$ model, in which the coordinates are independently active with probability $1/2$. For the five Classic McEliece parameter sets, our method reduces the estimated key-recovery cost by $14.09$--$41.19$ bits in the all-one model and by $7.25$--$22.48$ bits in the Bernoulli$(1/2)$ model.
- Abstract（参考訳）: Hemmert の Classic McEliece のキー-リカバリアルゴリズムは高次消滅に基づいている。
これは$\ker(\widetilde\varphi_A^{(p)})$を計算し、$A=H'''$は攻撃で使用される短縮パリティチェック行列である。
古典的なMcElieceパラメータの場合、このカーネル計算は攻撃の主要なコストである。
ブール格子上の重み付き上ゼータ変換として,$\widetilde\varphi_A^{(p)}$を定義する和を列単位で評価できることを示す。
これらの変換の選択レベルのみが$\widetilde\varphi_A^{(p)}$によって要求されるため、レベル$p$と最低要求レベルの間のバンドに対する評価を制限することで、$\widetilde\varphi_A^{(p)}$と変換の両方の正確な評価が得られる。
Wiedemann をベースとしたカーネル計算において, 結果として生じるゼータ変換評価を用いて, 全体のキー回復アルゴリズムを変更することなく, 繰り返し行列ベクトル積のコストを低減させる。
正確なコストは、非ピボット列の重量分布の$H''$に依存する。
したがって、2つのモデルを考える: すべての関連するバイナリ座標が活性なオールワンモデルと、それらの座標が確率1/2$で独立に活性なベルヌーイ$(1/2)$モデルである。
古典的な5つのパラメータ集合に対して、本手法は、全1モデルで14.09$--41.19$ビット、ベルヌーイモデルで7.25$--22.48$ビットと見積もられたキー-リカバリコストを7.25$--22.48$ビット削減する。
関連論文リスト
- Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
高次元データセットの各点における局所的な平均曲率の推定は、機械学習アルゴリズムの重要な要素である。
本稿では,このコストを桁違いに削減する2つの補完的貢献を紹介する。
実世界のデータセットの実験では、オリジナルの実装と比較して50倍から300倍のスピードアップが確認されている。
論文 参考訳（メタデータ） (2026-06-04T16:04:31Z) - Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。
我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文 参考訳（メタデータ） (2026-03-20T01:53:44Z) - Sublinear Time Quantum Algorithm for Attention Approximation [13.665266438908533]
本稿では,$mathrmAtt(Q, K, V)$の任意の行を,Q, K, V$への行クエリのみを用いて近似する量子データ構造を提案する。
我々のアルゴリズムはこれらの行列を$widetildeOleft( -1 n0.5 left( s_2.5 + s_1.5 d + 0.5 d right)$ timeで前処理する。
論文 参考訳（メタデータ） (2026-01-31T19:33:52Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Regression for matrix-valued data via Kronecker products factorization [0.5156484100374059]
我々は、パラメータ $beta_1k サブセット Rep times q_1$ および $beta_2k サブセット Rep times q$ を推定するための推定アルゴリズム KRO-PRO-FAC を提案する。
シミュレーションおよび実データに関する数値的研究は,提案手法が既存の手法と比較して,推定誤差と予測精度の両方において競合的であることを示している。
論文 参考訳（メタデータ） (2024-04-30T02:44:41Z) - OPORP: One Permutation + One Random Projection [37.6593006747285]
OPORPは、データ縮小/圧縮を達成するために、count-sketch'型のデータ構造の一種を使用する。
1つの重要なステップは、$k$サンプルを$l$標準に正規化することだ。
OPORPでは、(i)正規化と(ii)固定長ビンニングスキームの2つの重要なステップが、コサイン類似性を推定する精度を大幅に改善した。
論文 参考訳（メタデータ） (2023-02-07T14:45:34Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Coresets for Decision Trees of Signals [19.537354146654845]
仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。
これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
論文 参考訳（メタデータ） (2021-10-07T05:49:55Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。