扩展域Legendre PRF首次被破解：新型差分签名攻击恢复密钥

Legendre伪随机函数（PRF）因在多方计算和零知识证明协议中乘法复杂度低而备受重视。新论文首次全面分析了扩展域上单度Legendre PRF的安全性。

为什么Legendre PRF重要

• MPC效率 — 低乘法复杂度，适合安全计算协议
• ZKP友好 — 对零知识证明系统高效
• 扩展域 — 近期兴趣从素数域转向扩展域以提高实际效率

防御："无进位断裂"

将Legendre PRF扩展到扩展域时，多项式输入编码缺乏素数域实现中的"进位"效应，产生被认为能抵御经典滑动窗口碰撞攻击的异步"无进位断裂"。

突破

研究者发现无进位断裂本身是确定性周期性的。通过引入新型"差分签名"桶分技术：

• 对手可以系统地按结构形状分组断裂序列
• 完全绕过无进位防御
• 以O(U·p^r/M)次操作恢复密钥

启示

• 扩展域并非自动更安全 — 看似防御的无进位特性实际上可被利用
• 使用扩展域Legendre PRF的MPC/ZKP协议可能需要重新评估