論文の概要: Proximity Gaps for Gabidulin Codes and Applications
- arxiv url: http://arxiv.org/abs/2609.09838v1
- Date: Wed, 09 Sep 2026 07:45:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 19:44:08.941089
- Title: Proximity Gaps for Gabidulin Codes and Applications
- Title（参考訳）: ガビデュリン符号の確率ギャップとその応用
- Abstract要約: すべての$[n,k,d]$リニアランクメトリックコード$C$ over $mathbb F_qm$は、エラー$$との近接ギャップを許容することを示している。
ガビデュリン符号の場合、誤差10qn-1/qmで$(d-1)/(2n)$にギャップを拡大する。
これら2つの近接ギャップは、一般的な線形ハミング計量符号とリードリーブド符号と一致する。
次に、LigeroベースのPCSを一般の人に適応させ、$q$を得る。
- 参考スコア（独自算出の注目度）: 25.766490264515806
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Proximity gaps are central to the soundness of interactive oracle proofs of proximity (IOPPs) and polynomial commitment schemes (PCSs). An $[n,k,d]$ linear code $C\subseteq\mathbb F^n$ has a $δ$-proximity gap with error $ε$ if, for every $u_0,u_1\in\mathbb F^n$, either all points on $\ell_{u_0,u_1}=\{u_0+αu_1:α\in\mathbb F\}$ are $δ$-close to $C$, or at most an $ε$ fraction are. Although proximity gaps for Hamming-metric codes are well understood, their rank-metric counterparts remain largely unexplored despite their applications in coding theory and cryptography. In this work, we study proximity gaps for linear rank-metric codes and their cryptographic applications. First, we show that every $[n,k,d]$ linear rank-metric code $C$ over $\mathbb F_{q^m}$ admits a proximity gap for every $δ\le(d-1)/(3n)$, with error at most $q^{e+1}/q^m$, where $e=\lfloorδn\rfloor$. For Gabidulin codes, we improve the gap to $(d-1)/(2n)$ with error $10q^{n-1}/q^m$. These two proximity gaps match those for general linear Hamming-metric codes and Reed--Solomon (RS) codes, respectively. We prove the $(d-1)/(2n)$ bound is tight by constructing an infinite family of constant-rate Gabidulin codes and affine lines $\ell_{u_0,u_1}$ on which a $1-o(1)$ fraction of points are $d/(2n)$-close to the code, while $u_1$ is at least $3d/(4n)$-far from it. At the $d/(3n)$ gap, we also give a counterexample establishing a lower bound on $ε$. As applications, we construct an IOPP for interleaved Gabidulin codes by adapting the Ligero IOPP for interleaved RS codes. We then adapt the Ligero-based PCS for ordinary polynomials to obtain a $q$-linearized polynomial commitment scheme. To our knowledge, this is the first PCS framework based on rank-metric error-correcting codes.
- Abstract（参考訳）: 近接性証明 (IOPPs) と多項式コミットメントスキーム (PCSs) の音響性の中心である。
for every $u_0,u_1\in\mathbb F^n$, for all points on $\ell_{u_0,u_1}=\{u_0+αu_1:α\in\mathbb F\}$ are $δ$-close to $C$, orly a $ε$ fraction is。
ハミング測度符号の近接ギャップはよく理解されているが、符号化理論や暗号学に応用されているにもかかわらず、それらのランク測度符号はほとんど探索されていない。
本研究では,線形階調符号の近接ギャップとその暗号応用について検討する。
まず、すべての$[n,k,d]$ 線型階数計量コード $C$ over $\mathbb F_{q^m}$ はすべての $δ\le(d-1)/(3n)$ に近接ギャップを認め、誤差は最大$q^{e+1}/q^m$ で、$e=\lfloorδn\rfloor$ となる。
ガビデュリン符号の場合、誤差10q^{n-1}/q^m$で$(d-1)/(2n)$となる。
これら2つの近接ギャップはそれぞれ、一般的な線形ハミング計量符号とリード・ソロモン符号と一致する。
定数レートのガビデュリン符号とアフィンラインの無限族を構成することで、$(d-1)/(2n)$束がきついことを証明し、その上で1-o(1)$個の点が$d/(2n)$-クロースであり、$u_1$は少なくとも$3d/(4n)$-farである。
d/(3n)$ギャップでは、$ε$の低い境界を確立する反例を与える。
アプリケーションとして、インターリーブされたガビデュリン符号に対して、インターリーブされたRS符号に対してLigero IOPPを適用することにより、インターリーブされたガビデュリン符号のためのIOPPを構築する。
次に、通常の多項式に対してLigero-based PCSを適用し、$q$の線形化多項式コミットメントスキームを得る。
我々の知る限り、これはランクメトリックエラー訂正符号に基づく最初のPCSフレームワークである。
関連論文リスト
- A Note on Binary Quadratic Systems and their relation to complexity theory [0.0]
Q_d$の評価マトロイドの基底集合として$(FF_2)n$を証明します。
また、ホイットニー型符号反転の帰納法を用いて、マトロイドポートの要素から$_1/2n$以下に$_1/2n$をプッシュできる条件のみを示す。
論文 参考訳（メタデータ） (2026-09-07T17:19:05Z) - Quantum Codes from $r$-Nearly Self-Orthogonal Linear Codes via Jordan Canonical Form over $\mathbb{F}_{q^2}$ [5.6342405886627]
我々は、$F_q2$を超える任意の古典的線形符号から$q$ary量子安定化器符号を構築するためのヨルダン標準形式フレームワークを導入する。
このフレームワークは、双対を含む条件(すなわち自己直交性)を満たすために古典的な線形コード$mathcalC$を必要としない。
この構成を古典的な符号に適用すると、グラスルの表でよく知られたパラメータを改善または補足するいくつかの記録量子符号が生成される。
論文 参考訳（メタデータ） (2026-07-14T00:58:42Z) - Generalized Extended Codes with Applications in Entanglement-Assisted Qubit and Qutrit Codes [34.65128303335464]
一般化された拡張コードは、$Cperp_rm H$の第2種類の拡張コードと密接に関連しているコードのエルミート双対と単項的に等価であることを示す。
予測されるエルミート船体次元とエルミート船体距離を独立に制御するための明確な基準をC(bf u,a)$とする。
論文 参考訳（メタデータ） (2026-07-02T13:41:14Z) - Discrepancy for Random Linear Codes [10.105438043325357]
ランダムな線形符号は、幅広い状況下でほぼ最適な相違性を持つことを示す。
まず、ランダムな線形符号は、容量以上のエラーからリスト復号する非構造化のランダム符号と一致する。
第二に、素体上のランダム線形符号はゼロエラーリストのキャパシティ上の非構造化ランダム符号と一致する。
論文 参考訳（メタデータ） (2026-06-23T12:01:54Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。
効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。
また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文 参考訳（メタデータ） (2025-02-25T19:08:26Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Block Circulant Codes with Application to Decentralized Systems [12.014314088945968]
我々は,分散消去復号化をサポートするブロック循環符号のファミリ[n,k,d]を開発する。
このコードは、ブロックチェーンネットワークのデータ可用性問題に対処するプロトコルで使用するのに理想的だ。
論文 参考訳（メタデータ） (2024-06-18T00:22:20Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case [3.729242965449096]
We consider streaming algorithm for Approximating the value of Unique Games on a hypergraph with $t$-size hyperedges。
この値の$(r-varepsilon)$-approximationを達成する逆モデルの全てのストリーミングアルゴリズムは、$Omega(n1-2/t)$量子空間を必要とする。
論文 参考訳（メタデータ） (2021-09-06T16:56:19Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。