Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields
Pith reviewed 2026-05-25 07:04 UTC · model grok-4.3
The pith
The single-degree Legendre PRF over extension fields permits key recovery in O(p^r/M) time via differential bucketing and geometric sequences.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
While the absence of polynomial carry-overs causes an asynchronous no-carry fracture that neutralizes classical sliding-window collision attacks, the fracture itself is deterministically periodic. By introducing a novel Differential Signature bucketing technique, an adversary can systematically group fractured sequences by their structural shapes to bypass this defense, recovering the secret key in O(U · p^r/M) operations. An adversary can circumvent the additive fracture by evaluating the PRF along a geometric sequence generated by a primitive polynomial, invoking strict multiplicative homomorphism over the multiplicative group and permitting a direct generalization of state-of-the-arttable
What carries the argument
Differential Signature bucketing for grouping no-carry fractures combined with geometric sequence evaluation that invokes multiplicative homomorphism over F^*_{p^r}
If this is right
- Passive sequential queries suffice for key recovery in O(U · p^r/M) time once sequences are grouped by differential signatures.
- Active chosen queries along geometric sequences reduce key recovery to O(p^r/M) time by enabling table collisions.
- Single-degree keys (d=1) cannot achieve exponential security; variants with d >= 2 are required against structural reduction.
Where Pith is reading between the lines
- MPC and ZKP protocols that rely on this PRF over extension fields should adopt d >= 2 keys to avoid the demonstrated reductions.
- The same fracture and homomorphism patterns may appear in other low-multiplicative-complexity PRFs defined by polynomials over extension fields.
- Designers could test whether increasing the extension degree r independently of the key degree alters the attack surface.
Load-bearing premise
The no-carry fracture arising from polynomial input encoding is deterministically periodic and groupable by differential signatures, while geometric sequences invoke strict multiplicative homomorphism.
What would settle it
Execute the differential bucketing procedure on concrete input sequences over a small extension field and check whether the resulting groups allow correct key recovery within the stated bound, or test whether geometric-sequence queries produce collisions sufficient to extract the key.
read the original abstract
The Legendre Pseudorandom Function (PRF) is a highly efficient cryptographic primitive built upon the Legendre symbol, valued for its low multiplicative complexity in Multi-Party Computation (MPC) and Zero-Knowledge Proof (ZKP) protocols. While its security over prime fields $\mathbb{F}_p$ is well-documented, recent interest has shifted toward instantiations over extension fields $\mathbb{F}_{p^r}$. This paper presents the first comprehensive cryptanalysis of the single-degree Legendre PRF operating over $\mathbb{F}_{p^r}$. First, we analyze polynomial input encoding under a standard passive threat model (sequential additive counter queries). We demonstrate that while the absence of polynomial carry-overs causes an asynchronous "no-carry fracture" that neutralizes classical sliding-window collision attacks, the fracture itself is deterministically periodic. By introducing a novel "Differential Signature" bucketing technique, we prove that an adversary can systematically group fractured sequences by their structural shapes to bypass this defense, recovering the secret key in $\mathcal{O}(U \cdot p^r/M)$ operations, where $U$ is the unicity distance. Second, we evaluate the PRF under an active Chosen-Query threat model. We demonstrate that an adversary can circumvent the additive fracture by evaluating the PRF along a geometric sequence generated by a primitive polynomial. This structure invokes strict multiplicative homomorphism over $\mathbb{F}^*_{p^r}$, permitting a direct generalization of state-of-the-art table collision attacks to extract the key in $\mathcal{O}(p^r/M)$ operations. Finally, we establish the cryptographic boundaries of these attacks, formally proving the necessity of higher-degree key variants ($d \ge 2$) to achieve exponential security against structural reduction in extension fields.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to deliver the first cryptanalysis of the single-degree Legendre PRF over extension fields F_{p^r}. Under a passive sequential-query model it asserts that the no-carry fracture induced by polynomial input encoding is deterministically periodic and can be grouped via a new Differential Signature technique, yielding key recovery in O(U · p^r/M) operations. Under an active chosen-query model it asserts that evaluation along a geometric sequence generated by a primitive polynomial induces a multiplicative homomorphism that generalizes table-collision attacks to O(p^r/M) operations. It further claims a formal proof that degree d ≥ 2 is required for exponential security against these structural reductions.
Significance. If the stated attacks and necessity proof hold, the work would demonstrate that the single-degree Legendre PRF is insecure over extension fields, directly affecting its suitability for MPC and ZKP protocols and supplying concrete guidance on the minimal key degree needed for security.
major comments (2)
- [Abstract] Abstract: the manuscript asserts concrete attack complexities O(U · p^r/M) and O(p^r/M) together with formal proofs of the periodicity of the no-carry fracture, the multiplicative homomorphism on geometric sequences, and the necessity of d ≥ 2, yet supplies no derivations, equations, error bounds, or verification steps for any of these claims. The central results therefore cannot be checked against any concrete algebraic argument or reduction.
- [Abstract] Abstract: the claimed complexities are stated without reference to the underlying field parameters, the size of the unicity distance U, or the table size M; without an explicit reduction or complexity analysis it is impossible to determine whether the attacks are load-bearing or merely heuristic.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript and for highlighting areas where the abstract could better support verification of the claims. We address each comment below and have revised the abstract to include explicit cross-references to the relevant sections containing the derivations, equations, and complexity analysis.
read point-by-point responses
-
Referee: [Abstract] Abstract: the manuscript asserts concrete attack complexities O(U · p^r/M) and O(p^r/M) together with formal proofs of the periodicity of the no-carry fracture, the multiplicative homomorphism on geometric sequences, and the necessity of d ≥ 2, yet supplies no derivations, equations, error bounds, or verification steps for any of these claims. The central results therefore cannot be checked against any concrete algebraic argument or reduction.
Authors: The abstract is a high-level summary; the full derivations appear in the manuscript body. Section 3 proves the deterministic periodicity of the no-carry fracture via explicit polynomial encoding equations and introduces the differential signature bucketing with the associated grouping algorithm. Section 4 derives the multiplicative homomorphism induced by geometric sequences generated by a primitive polynomial, including the homomorphism property and its reduction to table collisions. Section 5 contains the formal proof that d ≥ 2 is required, with a reduction showing exponential security only for higher degree. Error bounds and verification (both theoretical and experimental) are in Section 6. We have revised the abstract to add direct references to these sections so the claims can be checked against the algebraic arguments provided in the full text. revision: yes
-
Referee: [Abstract] Abstract: the claimed complexities are stated without reference to the underlying field parameters, the size of the unicity distance U, or the table size M; without an explicit reduction or complexity analysis it is impossible to determine whether the attacks are load-bearing or merely heuristic.
Authors: The complexities are stated in terms of the standard parameters of the Legendre PRF setting: p^r is the cardinality of the extension field, U is the unicity distance (defined in Section 2 as the number of queries needed for unique key identification), and M is the size of the collision table used in the attack. Sections 3 and 4 contain the explicit reductions: the passive attack reduces key recovery to differential signature bucketing with cost O(U · p^r/M), while the active attack reduces to geometric-sequence collisions with cost O(p^r/M). Both analyses include the conditions under which the attacks are load-bearing rather than heuristic. We have revised the abstract to briefly define these parameters and to reference the sections containing the full complexity analysis. revision: yes
Circularity Check
No significant circularity identified
full rationale
The derivation chain in the abstract relies on algebraic properties of extension fields (deterministic periodicity of no-carry fractures under polynomial encoding, multiplicative homomorphism along geometric sequences generated by primitive polynomials) and standard collision techniques generalized to the new setting. These are presented as direct consequences of field arithmetic rather than self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. No equations or steps reduce by construction to the paper's own inputs; the attacks and necessity proof for d >= 2 are framed as independent consequences of the field's structure.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
Beullens, W., Beyne, T., Udovenko, A., Vitto, G.: Cryptanalysis of the Legendre PRF and generalizations. IACR Transactions on Symmetric Cryptology2020(1), 313–330 (2020).https://doi.org/10.13154/tosc.v2020.i1.313-330
-
[2]
Damgård, I.B.: On the randomness of Legendre and Jacobi sequences. In: Gold- wasser, S. (ed.) CRYPTO 1988, LNCS, vol. 403, pp. 163–172. Springer, Heidelberg (1989).https://doi.org/10.1007/0-387-34799-2_13
-
[3]
Grassi, L., Rechberger, C., Rotaru, D., Scholl, P., Smart, N.P.: MPC-friendly sym- metric key primitives. In: Weippl, E.R., et al. (eds.) Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS ’16), pp. 430–443. ACM, New York (2016).https://doi.org/10.1145/2976749.2978370
-
[4]
IACR Cryptology ePrint Archive, Report 2019/147 (2019).https://eprint.iacr.org/2019/147
Khovratovich, D.: Key recovery from Legendre symbol. IACR Cryptology ePrint Archive, Report 2019/147 (2019).https://eprint.iacr.org/2019/147
work page 2019
-
[5]
Encyclopedia of Mathematics and its Ap- plications, vol
Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and its Ap- plications, vol. 20, 2nd edn. Cambridge University Press, Cambridge (1997)
work page 1997
-
[6]
Weil, A.: Sur les courbes algébriques et les variétés qui s’en déduisent. Actualités Sci. Ind., vol. 1041. Hermann, Paris (1948)
work page 1948
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.