🔢 mathematics

Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

本文首次对扩展域上的勒让德伪随机函数进行了全面密码分析，揭示了其在被动和主动攻击模型下的结构性漏洞，证明了现有单度方案存在密钥恢复风险，并论证了采用高阶密钥变体以实现指数级安全性的必要性。

原作者： Daksh Pandey

发布于 2026-04-07

📖 1 分钟阅读🧠 深度阅读

原作者： Daksh Pandey

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文主要讲的是：一种原本被认为很安全的“数字锁”（Legendre 伪随机函数），当它被搬到一个更复杂的数学世界（扩展域）里使用时，竟然被轻易地破解了。

为了让你更容易理解，我们可以把这篇论文的内容想象成**“在一个特殊的迷宫里找钥匙”**的故事。

1. 背景：什么是“数字锁”？

想象一下，你有一个超级高效的数字锁（Legendre PRF）。

它的作用：用来保护隐私，比如在多人合作计算（MPC）或零知识证明（ZKP）中，确保大家能验证数据而不泄露秘密。
它的特点：计算速度极快，因为它用的数学规则很简单（就像只用加减法，不用复杂的乘除法）。
原来的用法：以前，这个锁是在一个普通的“整数迷宫”（素数域 $\mathbb{F}_p$ ）里用的。大家发现，如果你按顺序走（1, 2, 3...），攻击者很容易通过观察规律找到钥匙。

2. 新尝试：搬到“扩展迷宫”

为了跑得更快，工程师们决定把这个锁搬到**“扩展迷宫”**（扩展域 $\mathbb{F}_{p^r}$ ）里。

什么是扩展迷宫？ 想象原来的迷宫是直线的，现在的迷宫变成了多层立体结构。这里的“数字”不再是简单的整数，而是像多项式（比如 $3x^2 + 2x + 1$ ）这样的复杂物体。
工程师的防御策略：他们以为，因为这里的加法很特殊（没有进位），当你从 $x$ 走到 $x+1$ 时，不会像普通加法那样产生“进位”（比如 9 加 1 变成 10）。这种“没有进位”的断裂，应该能打断攻击者寻找规律的链条，让他们无法使用旧的“滑动窗口”攻击法。

论文的核心发现就是：工程师的防御策略失效了！

3. 攻击者的两种破解方法

论文作者 Daksh Pandey 展示了两种破解这个新锁的方法，分别对应“被动观察”和“主动挑衅”。

方法一：被动观察——“拼凑碎片” (Differential Signature)

场景：攻击者只是静静地观察服务器生成的数字流，不主动提问。
工程师的错觉：因为“没有进位”，数字序列看起来断断续续，像碎了一地的玻璃，无法连成一条直线。
攻击者的绝招（差分签名）：
- 攻击者发现，虽然玻璃碎了，但碎片的形状是有规律的！就像拼图一样，虽然位置乱了，但每一块碎片的边缘形状（差分签名）是固定的、周期性的。
- 攻击者发明了一种**“形状分类桶”**技术。他把所有观察到的碎片，按照它们的“边缘形状”分类放进不同的桶里。
- 结果：一旦把形状相同的碎片聚在一起，原本断裂的序列就重新连起来了。攻击者就能像拼拼图一样，反向推导出钥匙（秘密密钥）。
- 代价：这种方法需要观察大量的数据，但理论上可行。

方法二：主动挑衅——“走几何路线” (Geometric Sequences)

场景：攻击者可以主动向服务器提问（选择查询）。
工程师的防御：以为只要不让攻击者按顺序走（1, 2, 3...），他们就没法利用规律。
攻击者的绝招（几何序列）：
- 攻击者不再走“加法路线”（1, 2, 3...），而是走“乘法路线”（比如 $g, g^2, g^3...$ ，就像在迷宫里沿着螺旋楼梯走）。
- 魔法时刻：在这个特殊的数学世界里，乘法具有完美的“同构性”（Homomorphism）。这意味着，当你沿着螺旋楼梯走时，锁的内部结构会像变魔术一样，把复杂的钥匙拆解成一个简单的“旋转角度”和一个“正负号”。
- 结果：攻击者利用这种完美的数学性质，直接跳过了所有复杂的防御。他们只需要建立一个巨大的“参考地图”（哈希表），然后拿着自己生成的螺旋路线去比对，就能瞬间找到钥匙。
- 代价：这种方法比被动观察快得多，几乎可以瞬间破解。

4. 结论与未来：我们需要更复杂的锁

这篇论文得出了一个令人震惊的结论：
在扩展域中，使用“单级”（一次多项式）的 Legendre 锁是完全不安全的。 无论是被动观察还是主动攻击，攻击者都能轻松破解。

怎么办？
论文建议，必须把锁升级成**“多级”**（ $d \ge 2$ ）的版本。

比喻：原来的锁只是用一根棍子（一次多项式）挡路，攻击者很容易把棍子折断或绕过去。
新方案：现在要用一个复杂的齿轮组（二次或更高次多项式，比如 $x^2 + K_1x + K_0$ ）。
为什么有效？ 在齿轮组里，加法、乘法和旋转互相纠缠在一起，攻击者再也无法像之前那样简单地“拆解”或“分类”了。虽然攻击者可能还能用更高级的数学技巧（如“中间相遇”攻击）来尝试破解，但难度会从“容易”变成“几乎不可能”（指数级增长）。

总结

这篇论文就像是一个安全审计员，他告诉工程师们：

“你们以为把锁搬到更复杂的迷宫里，利用‘没有进位’的特性就能防住小偷。结果发现，小偷不仅没被难住，反而利用迷宫的特殊结构（周期性形状和乘法规律），找到了更简单、更直接的偷钥匙方法。

唯一的解决办法是：把锁做得更复杂（使用高次多项式），让小偷再也找不到简单的规律可循。"

一句话总结：在扩展域中，简单的 Legendre 锁已被攻破，必须使用更复杂的高次多项式版本才能保障安全。

论文技术总结：扩展域上勒让德伪随机函数的密码分析

论文标题：Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields（扩展域上勒让德伪随机函数的密码分析）
作者：Daksh Pandey (印度理工学院鲁尔基分校)
核心主题：针对在扩展域 $\mathbb{F}_{p^r}$ 上运行的单次数（ $d=1$ ）勒让德伪随机函数（PRF）的结构性漏洞分析，揭示了其在被动和主动攻击模型下的不安全性。

1. 研究背景与问题 (Problem)

背景：勒让德 PRF 因其极低的乘法复杂度，在多_party_计算（MPC）和零知识证明（ZKP）协议中备受青睐。传统的勒让德 PRF 定义在素数域 $\mathbb{F}_p$ 上，但为了优化特定协议的吞吐量，近期研究开始尝试将其部署在扩展域 $\mathbb{F}_{p^r}$ 上。
问题：虽然 $\mathbb{F}_p$ $F_{p}$ 上的安全性已有广泛研究，但 $\mathbb{F}_{p^r}$ $F_{p^{r}}$ 上的安全性尚不明确。
- 在扩展域中，整数计数器被编码为多项式。由于多项式加法在系数上模 $p$ 运算且没有进位（no-carry），导致传统的滑动窗口碰撞攻击（Sliding-window collision attacks）所需的连续差分被破坏，形成所谓的“无进位断裂”（no-carry fracture）。
- 核心问题：这种“无进位断裂”是否足以提供足够的安全性？是否存在新的攻击向量可以利用扩展域的代数结构来恢复密钥？

2. 方法论 (Methodology)

论文提出了两种主要的攻击模型来评估单次数（ $d=1$ ）勒让德 PRF 的安全性：

A. 被动攻击模型 (Passive Threat Model)

场景：攻击者仅能观察到服务器生成的密钥流（基于顺序递增的整数计数器 $n$ 映射到多项式 $X_n$ ）。
观察：
- 虽然 $X_{n+1} - X_n$ 不再是常数 1，而是取决于 $n+1$ 的 $p$ 进估值，导致差分序列呈现非连续的“断裂”。
- 然而，这种差分序列是确定性且周期性的。
技术：
- 差分签名（Differential Signature）：定义了一个基于窗口内累积多项式差分的签名 $\delta_n$ 。
- 分桶技术（Bucketing）：攻击者根据差分签名的“形状”将密钥流中的窗口分组。由于签名数量有限，攻击者可以将具有相同差分形状的窗口聚类。
- 密钥恢复：通过哈希表匹配，利用聚类后的窗口进行碰撞攻击，从而恢复密钥。

B. 主动攻击模型 (Active Chosen-Query Threat Model)

场景：攻击者可以主动选择输入查询。
策略：
- 放弃多项式加法，转而利用扩展域乘法群 $\mathbb{F}^*_{p^r}$ 的性质。
- 选择原根生成元 $g(x)$ ，构造几何序列查询 $X_i = g^i$ 。
技术：
- 乘法同态性（Multiplicative Homomorphism）：利用勒让德符号的完全乘法性质，将 $L(g^i + K)$ 分解为 $L(K) \cdot L(g^{i+j} + 1)$ 。
- 因子分解：该表达式将未知密钥 $K$ 转化为一个未知的指数偏移量 $j$ 和一个符号系数。
- 几何表碰撞攻击：攻击者生成参考序列 $L(g^m + 1)$ ，并在哈希表中查找与观测到的密钥流窗口（或其按位取反）的匹配。一旦匹配，即可通过离散对数关系 $j = m - i$ 恢复密钥。

3. 主要贡献 (Key Contributions)

首次全面分析：提供了针对扩展域 $\mathbb{F}_{p^r}$ 上单次数勒让德 PRF 的首次系统性密码分析。
揭示“无进位断裂”的局限性：证明了虽然多项式编码破坏了连续差分，但其内在的周期性使得攻击者可以通过“差分签名”分桶技术绕过这一防御，实现被动密钥恢复。
提出几何序列攻击：发现通过几何序列查询可以完全绕过加法群的断裂限制，利用乘法同态性将问题简化为指数偏移问题，从而将主动攻击复杂度降至理论下限。
形式化安全边界：证明了单次数（ $d=1$ ）方案在扩展域下是完全不安全的，并论证了使用高次数（ $d \ge 2$ ）多项式变体的必要性。

4. 研究结果 (Results)

被动攻击复杂度：
- 攻击者可以在 $O(U \cdot p^r / M)$ 的操作复杂度内恢复密钥，其中 $U$ 是唯一性距离（unicity distance）， $M$ 是观测到的比特数。
- 这意味着只要观测到足够多的数据，被动攻击是可行的。
主动攻击复杂度：
- 攻击者可以在 $O(p^r / M)$ 的操作复杂度内恢复密钥。
- 该复杂度仅取决于域大小和查询数量，完全消除了“无进位”带来的保护，将安全性降低到了理论最低点。
高次数变体（ $d \ge 2$ ）：
- 对于 $d \ge 2$ 的情况（如二次多项式 $x^2 + K_1x + K_0$ ），几何序列攻击无法将表达式分解为常数与参考序列的乘积。
- 中间项（如 $K_1x$ ）将序列绑定在特定的密钥组合上，使得 $O(p^r/M)$ 的碰撞攻击失效。
- 初步分析表明，即使对于 $d=2$ ，可能需要 $O(p^r)$ 的优化搜索，而 $d \ge 3$ 或 $4$ 才能提供指数级的安全边际。

5. 意义与结论 (Significance & Conclusion)

安全性警示：本文形式化地打破了扩展域上单次数勒让德 PRF 的安全性假设。对于 MPC 和 ZKP 应用，如果直接沿用 $\mathbb{F}_p$ 上的设计逻辑而仅扩展到 $\mathbb{F}_{p^r}$ 而不改变多项式次数，将导致严重的安全漏洞。
设计建议：
- 在扩展域部署勒让德 PRF 时，必须使用高次数密钥变体（ $d \ge 2$ ，建议 $d \ge 3$ 或 $4$）。
- 高次数多项式通过引入非线性项，破坏了攻击者利用乘法同态性进行因子分解的能力，从而抵抗结构性归约攻击。
未来工作：论文指出了针对 $d \ge 2$ 变体的进一步研究方向，如利用 Tschirnhaus 变换和“配方法”消除中间系数，以及应用中间相遇（Meet-in-the-Middle）攻击来评估其实际安全边界。

总结：该论文揭示了扩展域上多项式编码的“无进位”特性并非安全屏障，反而可能被利用。通过巧妙的代数变换（被动下的差分签名聚类，主动下的几何序列同态），攻击者可以高效恢复密钥。这为下一代基于勒让德符号的密码原语设计提供了关键的安全指导：在扩展域中，必须增加多项式次数以维持安全性。