Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

• URL: http://arxiv.org/abs/2604.04833v2
• Date: Wed, 08 Apr 2026 13:27:39 GMT
• Title: Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields
• Abstract summary: The Legendre Pseudorandom Function (PRF) is a highly efficient cryptographic primitive built upon the Legendre symbol.<n>Recent interest has shifted toward instantiations over extension fields $mathbbF_pr$.<n>This paper presents the first comprehensive cryptanalysis of the single-degree Legendre PRF operating over $mathbbF_pr$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Limit Properties at Critical Indices of Linear Canonical Riesz Potentials and Their Applications to Security of Multi-Image Encryption [5.1237838533028155]
  This article introduces the linear canonical Riesz potential (for short, LCRP) and gives its symbol in terms of linear canonical transforms.<n> Driven by image processing, we establish the convergence/divergence of these LCRPs for different kinds of functions.<n>We propose an asymmetric cascaded LCRP method for the multi-image encryption and create an efficient and secure cryptosystem.
  arXiv  Detail & Related papers  (2026-05-03T00:31:00Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Cryptographic transformations over polyadic rings [3.0860863056832826]
  cryptosystems rely on binary operations within groups, rings, or fields.<n>We propose a shift to polyadic rings, which generalize classical rings by allowing operations of higher arity.<n>We present two concrete encryption procedures that leverage this structure.
  arXiv  Detail & Related papers  (2025-12-14T07:15:55Z)
• Semigroup action based on skew polynomial evaluation with applications to Cryptography [0.0]
  We introduce an action of the skew ring $mathbbF_q[X;, right]$ over $mathbbF_q$ based on its valuation and the concept of left skew product of functions.<n>We exploit this fact in order to build a public key exchange protocol that is secure in Canetti and Krawczyk model.
  arXiv  Detail & Related papers  (2025-12-02T10:08:50Z)
• A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group [0.0]
  We propose a symmetric-key cryptosystem whose linear action takes place instead in the Burnside ring $A(G)$ of a compact Lie group $G$.<n>Messages of arbitrary finite length are encoded as finitely supported elements of $A(G)$ and encrypted via the Burnside product with $k$.<n>We show that any finite set of observations constrains the action only on a finite-rank submodule $W_Lsubset A(O(2))$, and we show information-theoretic non-identifiability of the key from such data.
  arXiv  Detail & Related papers  (2025-10-13T01:57:22Z)
• Low-degree lower bounds via almost orthonormal bases [47.83594448785856]
  Low-degrees have emerged as a powerful paradigm for providing evidence of statistical--computational gaps across a variety of high-dimensional statistical models.<n>In this work, we propose a more direct proof strategy.
  arXiv  Detail & Related papers  (2025-09-11T11:07:36Z)
• Extended c-differential distinguishers of full 9 and reduced-round Kuznyechik cipher [1.4407799786341453]
  We introduce truncated $c$-differential analysis against the full 9-round Kuznyechik cipher with no key pre-whitening.<n>This is the first practical distinguisher against a full 9-round Kuznyechik variant.
  arXiv  Detail & Related papers  (2025-07-02T22:27:33Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.