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.
Elliptic Curve Cryptography (ECC) is a fundamental component of modern public-key cryptosystems that enable efficient and secure digital signatures, key exchanges, and encryption. Its core operation, scalar multiplication, denoted as $k \cdot P$, where $P$ is a base point and $k$ is a private scalar, relies heavily on the secrecy and unpredictability of $k$. Conventionally, $k$ is selected using user input or pseudorandom number generators. However, in resource-constrained environments with weak entropy sources, these approaches may yield low-entropy or biased scalars, increasing susceptibility to side-channel and key recovery attacks. To mitigate these vulnerabilities, we introduce an optimization-driven scalar generation method that explicitly maximizes bit-level entropy. Our approach uses differential evolution (DE), a population-based metaheuristic algorithm, to search for scalars whose binary representations exhibit maximal entropy, defined by an even and statistically uniform distribution of ones and zeros. This reformulation of scalar selection as an entropy-optimization problem enhances resistance to entropy-based cryptanalytic techniques and improves overall unpredictability. Experimental results demonstrate that DE-optimized scalars achieve entropy significantly higher than conventionally generated scalars. The proposed method can be integrated into existing ECC-based protocols, offering a deterministic, tunable alternative to traditional randomness, ideal for applications in blockchain, secure messaging, IoT, and other resource-constrained environments.
On June 2, 2024, Mexico held its federal elections. The majority of Mexican citizens voted in person at the polls in this historic election. For the first time though, Mexican citizens living outside their country were able to vote online via a web app, either on a personal device or using an electronic voting kiosk at one of 23 embassies and consulates in the U.S., Canada, and Europe. In total, 144,734 people voted outside of Mexico: 122,496 on a personal device and 22,238 in-person at a kiosk. Voting was open for remote voting from 8PM, May 18, 2024 to 6PM, June 2, 2024 and was open for in-person voting from 8AM-6PM on June 2, 2024. This article describes the technical and cryptographic tools applied to secure the ex-patriate component of the election and to enable INE (Mexico's National Electoral Institute) to generate provable election results within minutes of the close of the election. This article will also describe how the solutions we present scale to elections on a national level.
Pairings have been widely used since their introduction to cryptography. They can be applied to identity-based encryption, tripartite Diffie-Hellman key agreement, blockchain and other cryptographic schemes. The Acceleration of pairing computations is crucial for these cryptographic schemes or protocols. In this paper, we will focus on the Elliptic Net algorithm which can compute pairings in polynomial time, but it requires more storage than Miller's algorithm. We use several methods to speed up the Elliptic Net algorithm. Firstly, we eliminate the inverse operation in the improved Elliptic Net algorithm. In some circumstance, this finding can achieve further improvements. Secondly, we apply lazy reduction technique to the Elliptic Net algorithm, which helps us achieve a faster implementation. Finally, we propose a new derivation of the formulas for the computation of the Optimal Ate pairing on the twisted curve. Results show that the Elliptic Net algorithm can be significantly accelerated especially on the twisted curve. The algorithm can be $80\%$ faster than the previous ones on the twisted 381-bit BLS12 curve and $71.5\%$ faster on the twisted 676-bit KSS18 curve respectively.
Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Keewoo Lee
The scaled inverse of a nonzero element $a(x)\in \mathbb{Z}[x]/f(x)$, where $f(x)$ is an irreducible polynomial over $\mathbb{Z}$, is the element $b(x)\in \mathbb{Z}[x]/f(x)$ such that $a(x)b(x)=c \pmod{f(x)}$ for the smallest possible positive integer scale $c$. In this paper, we investigate the scaled inverse of $(x^i-x^j)$ modulo cyclotomic polynomial of the form $Φ_{p^s}(x)$ or $Φ_{p^s q^t}(x)$, where $p, q$ are primes with $p<q$ and $s, t$ are positive integers. Our main results are that the coefficient size of the scaled inverse of $(x^i-x^j)$ is bounded by $p-1$ with the scale $p$ modulo $Φ_{p^s}(x)$, and is bounded by $q-1$ with the scale not greater than $q$ modulo $Φ_{p^s q^t}(x)$. Previously, the analogous result on cyclotomic polynomials of the form $Φ_{2^n}(x)$ gave rise to many lattice-based cryptosystems, especially, zero-knowledge proofs. Our result provides more flexible choice of cyclotomic polynomials in such cryptosystems. Along the way of proving the theorems, we also prove several properties of $\{x^k\}_{k\in\mathbb{Z}}$ in $\mathbb{Z}[x]/Φ_{pq}(x)$ which might be of independent interest.
A cycle of elliptic curves is a list of elliptic curves over finite fields such that the number of points on one curve is equal to the size of the field of definition of the next, in a cyclic way. We study cycles of elliptic curves in which every curve is pairing-friendly. These have recently found notable applications in pairing-based cryptography, for instance in improving the scalability of distributed ledger technologies. We construct a new cycle of length 4 consisting of MNT curves, and characterize all the possibilities for cycles consisting of MNT curves. We rule out cycles of length 2 for particular choices of small embedding degrees. We show that long cycles cannot be constructed from families of curves with the same complex multiplication discriminant, and that cycles of composite order elliptic curves cannot exist. We show that there are no cycles consisting of curves from only the Freeman or Barreto--Naehrig families.