#LPN

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

← 返回所有主题
推荐 3.5
Conf: 50%
👥 作者: Divesh Aggarwal, Rishav Gupta, Li Zeyong

本文针对带噪声线性奇偶校验学习问题(LPN)及其稀疏变体证明了新的硬度放大结果。LPN问题是密码学中重要的平均情况困难问题,其困难性假设是许多密码方案安全性的基础。在标准LPN_{η,n,m}中,目标是从m个带噪声的线性样本中恢复秘密向量s∈F2^n,其中样本的噪声服从伯努利分布Ber(η)。作者基于Hirahara和Shimizu提出的直接积框架,展示了“实例分数放大”定理:对于任意ε,δ>0,任何以概率ε求解LPN_{η,n,m}的算法都可以转化为一个算法,在参数缩放后的相关LPN分布上以概率1-δ成功,其中缩放因子k=Θ((1/δ)log(1/ε))。等价地,能够在“小部分实例”上求解LPN的算法可以被转化为在“几乎所有实例”上求解LPN的算法,从而在广泛的参数范围内实现了自我放大。作者还将相同的放大方法扩展到有限域F_q上的LPN以及稀疏LPN(其中每个查询向量恰好有σ个非零项)。这些结果共同建立了一类广泛的LPN类型问题的困难性自我放大定理,加强了假定LPN及其稀疏变体在平均情况下困难的基础。适合密码学理论研究者、密码学安全基础方向的研究人员阅读。

💡 推荐理由: 本文为LPN问题的平均情况困难性提供了更强的理论支撑,有助于理解LPN假设的安全强度,对依赖LPN的密码方案的安全性评估有理论指导意义。

🎯 建议动作: 研究跟进

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)