#cryptographic-hardness

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

← 返回所有主题
👥 作者: Luis Adrián Lizama-Pérez

本文提出并研究了结构化 totient 原像(Structured Totient Preimage, STP)问题,这是一种带有直接密码学动机的受限重构关系。设 p1,...,pk 为具有相同比特长度的不同素数,仅公开 x = ∏(pi - 1),给定 (x, λ, k),STP 要求找到任意一组满足该乘积的 k 个不同的 λ 比特素数。该关系可高效验证,但其重构复杂度此前未知。作者建立了三项具体结果:第一,对于已分解的 x,他们导出了有序指数分配的精确数量,并给出一个界限,表明当 Ω(x) = O(log λ) 且 k 固定时,直接重构是多项式时间的,从而排除了该参数域作为强困难性基础的可能性;第二,他们给出了用于重构和碰撞分析的穷举算法;第三,他们穷举评估了 28 组参数对(2 ≤ k ≤ 5,λ 最高到 16),在最大普查中包含 4,588,935 个素数集合。数据通过碰撞参与度、最大重数和条件模糊位数量化了非单射性。这些结果将 STP 与一般的逆 totient 计算区分开来,并为明确增长的参数族提出结构化 totient 原像假设提供了依据。在该假设下,STP 成为一种候选的原像抵抗关系,其对承诺、乘法见证的知识证明以及认证方案的含义可以被精确表述。论文建立了这些构造的计算基础和参数约束,但并不声称提供安全归约或后量子安全性。

💡 推荐理由: 该研究为基于素数乘积结构的密码学原语提供了新的困难问题候选,有助于评估此类关系的安全性边界,并为设计承诺、知识证明和认证协议提供理论依据,值得密码学与安全研究人员关注。

🎯 建议动作: 研究跟进

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