🔢 mathematics

Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

This paper presents the first comprehensive cryptanalysis of the Legendre Pseudorandom Function over extension fields, demonstrating that both passive and active adversaries can efficiently recover the secret key by exploiting structural periodicities and multiplicative homomorphisms, thereby proving that higher-degree key variants are necessary to achieve exponential security.

Original authors: Daksh Pandey

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daksh Pandey

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Digital Lock That Was Too Simple

Imagine you have a high-tech digital lock (the Legendre Pseudorandom Function) used to secure secret communications in a group chat (Multi-Party Computation) or to prove you know a secret without revealing it (Zero-Knowledge Proofs).

For a long time, this lock worked great when the "keys" were just simple numbers (like 1, 2, 3). But recently, engineers decided to upgrade the lock to handle more complex "keys" made of polynomials (mathematical expressions with multiple parts, like $x^2 + 3x + 5$ ) to make it faster and more efficient.

The bad news: This paper says, "Stop! That new upgrade is broken." The authors found two different ways to pick this new lock without the key, proving it's not safe to use in its current form.

Analogy 1: The "No-Carry" Fracture (The Passive Attack)

The Setup:
Imagine you are trying to guess a secret code by watching a machine print out a long stream of 0s and 1s. The machine works by taking a counter (1, 2, 3, 4...) and adding a secret number to it, then checking if the result is "even" or "odd" (in a fancy math way).

The Old Way (Prime Fields):
In the old system, adding 1 to a number is smooth. 1, 2, 3, 4... it's a straight line. Attackers could look for patterns in this smooth line to guess the secret.

The New Way (Extension Fields):
The engineers thought, "Let's make the math harder by using polynomials." They imagined the numbers as blocks of Lego.

In normal math, if you have 9 blocks and add 1, it becomes 10 (you carry the 1 over to the next column).
In this new "polynomial" math, there is no carrying over. If you have a block that is "full," adding 1 just resets it to zero and adds a 1 to the next separate block.

The "Fracture":
The authors realized this "no-carry" rule creates a weird, jagged pattern. Instead of a smooth line, the sequence looks like a staircase that keeps breaking apart.

Analogy: Imagine a train moving on a track. In the old system, the track is smooth. In the new system, the track keeps jumping up and down randomly. The engineers thought, "Great! The attackers can't predict the jumps, so they can't guess the secret."

The Breakthrough:
The authors found that while the jumps look random, they actually follow a strict, repeating rhythm.

Analogy: It's like a broken clock that jumps forward 5 minutes, then 1 minute, then 5 minutes, then 1 minute. It looks chaotic, but if you watch long enough, you realize the pattern repeats every 6 minutes.
The Attack: The authors created a new tool called a "Differential Signature." Instead of trying to predict the next jump, they grouped the jumps by their "shape." They found that all the "jump-shapes" repeat in a cycle. By sorting the secret code's output into these shape-buckets, they could reverse-engineer the secret key much faster than anyone thought possible.

Analogy 2: The "Geometric Sequence" Hack (The Active Attack)

The Setup:
The first attack required the attacker to just sit and watch (Passive). But what if the attacker could ask the machine, "Hey, what happens if I give you this specific number?" (Active/Chosen-Query).

The Old Defense:
The engineers thought, "If you ask us for random numbers, we'll just add our secret to them. Since the math is so complex, you can't figure out our secret."

The Breakthrough:
The authors realized that while the "addition" math was broken, the "multiplication" math was still perfect.

Analogy: Imagine the secret lock is a combination of a spinning wheel and a sliding bar. The engineers thought, "If you push the bar (addition), it gets stuck in a weird way."
But the authors said, "What if we don't push the bar? What if we spin the wheel?"
They found a special sequence of numbers (a Geometric Sequence) where the math behaves beautifully. When you multiply these numbers, the secret key acts like a simple "shift" or "rotation" of the whole pattern.

The Attack:
By asking the machine for this specific spinning sequence, the attacker could use a "magic mirror" (multiplicative homomorphism) to see the secret key clearly.

Analogy: It's like trying to find a specific person in a crowd. The engineers thought, "If they walk in a zig-zag, you can't find them." The attacker said, "I'll just ask them to walk in a straight line." Once they walk in a straight line, the attacker can instantly spot them.
This allowed the attacker to crack the code almost instantly, ignoring all the complex "polynomial" defenses.

The Conclusion: What Should We Do?

The paper concludes that the current version of this lock (using simple polynomials, or degree $d=1$ ) is completely broken in this new environment. It's like building a house out of sand; it looks fancy, but the tide (the math) washes it away immediately.

The Solution:
To fix this, the authors suggest making the keys more complex.

Instead of a simple polynomial (like $x + K$ ), use a complex one (like $x^2 + K_1x + K_0$ ).
Analogy: If a simple lock can be picked by a straight line or a zig-zag, we need a lock that requires a 3D puzzle to open. By adding more layers (higher degrees), the "magic mirror" trick stops working because the math becomes too tangled to simplify.

Final Takeaway:
If you are building secure systems using this technology, do not use the simple version over these complex fields. You must use the more complex, "higher-degree" versions to stay safe. The paper provides the blueprints for how to break the weak version and the math to prove why the strong version is necessary.

1. Problem Statement

The Legendre Pseudorandom Function (PRF) is a cryptographic primitive valued for its low multiplicative complexity, making it highly efficient for Multi-Party Computation (MPC) and Zero-Knowledge Proofs (ZKP). While its security over prime fields ( $\mathbb{F}_p$ ) is well-studied, recent implementations have shifted to extension fields ( $\mathbb{F}_{p^r}$ ) to optimize throughput.

The core problem addressed is the security of the single-degree ( $d=1$ ) Legendre PRF over extension fields.

Context: In $\mathbb{F}_{p^r}$ , inputs are encoded as polynomials. Unlike integer arithmetic, polynomial addition in $\mathbb{F}_{p^r}$ operates coefficient-wise without "carry-over" to higher degrees.
Hypothesis: It was previously believed that this "no-carry" property would disrupt the continuous additive progressions required by classical sliding-window collision attacks, thereby securing the PRF against passive adversaries.
Objective: This paper challenges that assumption, aiming to determine if the structural fracture caused by the lack of carries can be exploited to recover the secret key, both passively and actively.

2. Methodology

The paper employs a combination of algebraic analysis, statistical bounding, and algorithmic cryptanalysis under two threat models:

A. Mathematical Foundations

Encoding: Integers $n$ are mapped to polynomials $X_n(x)$ via base- $p$ expansion.
The "No-Carry Fracture": The authors analyze the differential $\Delta_n = X_{n+1} \oplus X_n$ . In standard integers, this is always 1. In $\mathbb{F}_{p^r}$ , due to the lack of carry propagation, the differential is not constant but takes values from the set $\{x^k + 1\}$ , creating a "fractured" sequence of arithmetic sub-blocks.
Statistical Bounds: The paper utilizes the Hasse-Weil bound to prove that the keystream is statistically indistinguishable from a uniform distribution. This establishes that attacks cannot rely on statistical bias but must exploit algebraic structure.

B. Passive Threat Model (Sequential Queries)

Approach: The adversary observes a keystream generated by sequentially incrementing the input counter.
Technique: The authors introduce a "Differential Signature" bucketing technique.
- They define a signature $\delta_n$ as the sequence of cumulative polynomial differences relative to a starting point.
- Despite the "fracture," the sequence of differentials is deterministically periodic.
- The attacker groups observed keystream windows into equivalence classes based on their structural "shape" (signature).
- By matching these shapes against a precomputed hash table, the attacker can bypass the fracture and recover the key.

C. Active Threat Model (Chosen-Query)

Approach: The adversary can choose specific inputs to query the PRF.
Technique: The attacker abandons additive sequences and queries the PRF along a geometric sequence generated by a primitive element $g(x)$ of the multiplicative group $\mathbb{F}_{p^r}^*$ .
Algebraic Reduction:
- The Legendre symbol is completely multiplicative.
- The evaluation $L(g^i + K)$ can be factored into $L(K) \cdot L(g^{i+j} + 1)$ , where $j$ is a discrete logarithm shift.
- This transforms the problem into finding a shift $j$ in a universal reference sequence, effectively neutralizing the additive fracture entirely.

3. Key Contributions

First Comprehensive Analysis: This is the first paper to provide a full cryptanalysis of the single-degree Legendre PRF over extension fields ( $\mathbb{F}_{p^r}$ ).
Passive Attack (Shape Bucketing): Demonstrates that the "no-carry fracture" is not a defense but a deterministic periodicity. The authors propose a novel Differential Signature method to cluster fractured sequences, allowing passive key recovery.
Active Attack (Geometric Sequences): Proves that an active adversary can completely circumvent the additive limitations by using geometric queries. This invokes strict multiplicative homomorphism, reducing the problem to a simple shift search.
Complexity Breakdown:
- Passive Complexity: $O(U \cdot p^r / M)$ , where $U$ is the unicity distance and $M$ is the number of observed bits.
- Active Complexity: $O(p^r / M)$ . This matches the theoretical lower bound for table collision attacks, proving the single-degree variant is broken.
Security Boundaries: Establishes that higher-degree variants ( $d \ge 2$ ) are necessary. The paper argues that while $d=2$ resists the geometric factorization, it may still be vulnerable to optimized Meet-in-the-Middle (MITM) attacks, suggesting $d \ge 3$ or $4$ is required for robust security.

4. Results

Breaking $d=1$ : The single-degree Legendre PRF over $\mathbb{F}_{p^r}$ is completely insecure under both passive and active models. The "no-carry" property fails to provide security against structural analysis.
Efficiency: The active geometric attack reduces the security of the PRF to the complexity of a standard table collision attack, requiring only $O(p^r/M)$ operations.
Statistical Safety: The paper confirms that the PRF remains statistically random (no bias), meaning the attacks are purely algebraic and structural, not statistical.
Mitigation: The authors confirm that increasing the degree of the secret polynomial ( $d \ge 2$ ) prevents the multiplicative factorization used in the active attack. However, they warn that $d=2$ may still be vulnerable to $O(p^r)$ attacks, recommending $d \ge 3$ for exponential security margins.

5. Significance

Protocol Security: This work has immediate implications for MPC and ZKP protocols currently deploying or considering the Legendre PRF over extension fields for efficiency. It invalidates the security of the standard $d=1$ instantiation in these contexts.
Design Guidelines: The paper provides a critical design guideline: Extension fields do not automatically increase security for linear PRFs; in fact, they introduce specific algebraic structures (like the lack of carry) that can be exploited if the PRF degree is not increased.
Future Research: It sets a new baseline for cryptanalysis in extension fields, highlighting the need for higher-degree polynomials ( $d \ge 3$ ) and suggesting new research directions into Tschirnhaus transformations and algebraic reductions for higher-degree variants.
Reproducibility: The authors have made their Python implementations (including the geometric table collision and passive bucketing) open-source, facilitating immediate verification and further research.

Conclusion: The paper effectively demonstrates that the transition from prime fields to extension fields for the Legendre PRF is not a security upgrade for the single-degree variant but a vulnerability that allows for efficient key recovery. It mandates a shift to higher-degree polynomial constructions to maintain cryptographic safety.