#gabidulin-codes

共收录 1 条相关安全情报。

← 返回所有主题
推荐 8.5
Conf: 50%
👥 作者: Songsong Li, Chaoping Xing, Chen Yuan, Ruiqi Zhu

本论文研究秩度量(rank-metric)线性码的邻近性间隙(proximity gap)问题及其密码学应用。邻近性间隙是交互式 Oracle 邻近性证明(IOPP)与多项式承诺方案(PCS)可靠性(soundness)分析的核心概念:对于 [n,k,d] 线性码 C ⊆ F^n,若对任意 u0,u1 ∈ F^n,要么直线 ℓ_{u0,u1} = {u0 + αu1 : α ∈ F} 上的所有点都 δ-接近 C,要么至多 ε 比例的点 δ-接近 C,则称该码具有错误为 ε 的 δ-邻近性间隙。Hamming 度量下的邻近性间隙已被充分理解(对应一般线性码与 Reed–Solomon 码的经典结论),但秩度量情形尽管在编码理论与密码学中应用广泛,此前几乎未被探索,论文正是针对这一空白展开。 核心方法与结果:第一,作者证明任意 F_{q^m} 上的 [n,k,d] 线性秩度量码对每个 δ ≤ (d-1)/(3n) 都具有邻近性间隙,误差至多 q^{e+1}/q^m,其中 e = ⌊δn⌋;针对 Gabidulin 码这一重要子类,将间隙阈值改进到 (d-1)/(2n),误差为 10q^{n-1}/q^m。这两个界分别与一般线性 Hamming 度量码和 Reed–Solomon 码的对应结论相匹配,说明秩度量并不比 Hamming 度量更脆弱。第二,作者通过构造无限族常率(constant-rate)Gabidulin 码与仿射直线,证明 (d-1)/(2n) 这一界是紧的:在这些直线上有 1-o(1) 比例的点是 d/(2n)-接近码的,而 u1 本身至少是 3d/(4n)-远离码的;同时在 d/(3n) 间隙处给出反例,建立了对 ε 的下界。第三,作为应用,作者把面向交织 Reed–Solomon 码的 Ligero IOPP 适配到交织 Gabidulin 码,构造出相应 IOPP;并把基于 Ligero 的普通多项式承诺方案推广到 q-线性化多项式,得到 q-线性化多项式承诺方案。据作者所知,这是首个基于秩度量纠错码的 PCS 框架。 适合读者:编码理论、纠错码与密码学交叉方向的研究者,尤其是研究 IOPP/SNARK、多项式承诺与后量子密码方案设计的人员。

💡 推荐理由: 多项式承诺与 IOPP 是现代简洁证明系统(SNARK 类)的信任基石,其可靠性依赖于邻近性间隙这一精细代数条件。此前该分析几乎只在 Hamming 度量下完成,而秩度量码是后量子密码与网络编码的重要候选。论文首次系统给出 Gabidulin/秩度量码的间隙界并证明其紧性,还给出首个基于秩度量码的 PCS 框架,为证明系统与后量子方案设计开辟了新的可选基底,值得密码协议设计与审计人员跟踪。

🎯 建议动作: 研究跟进

排序因子: 影响边界/网络设备 (+5) | 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)