Smoothness of Shortest Isogenies to Frobenius Conjugates

arXiv:2610.21488 · math.NT, cs.CR · Submitted 2026-10-15 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: Today's paper: "Smoothness of Shortest Isogenies to Frobenius Conjugates".

Elias: The gist: The smoothness of shortest isogenies to Frobenius conjugates, denoted by δE, has been proven to be smooth,

Nadia: First, who's behind it and why it matters.

Paper summary: Nadia: So we're looking at this paper now called "Smoothness of Shortest Isogenies to Frobenius Conjugates".

Elias: Exactly. Basically, the authors are tackling the problem of how often the shortest isogeny, which they call delta E, between an elliptic curve E and its Frobenius conjugate E(p), has a smooth degree.

Priya: What does that mean in practice? Does it help us break things faster?

Nadia: It directly relates to Wesolowski's attack on the supersingular endomorphism ring problem.

Elias: Right, Wesolowski established that if we can find a B-smooth isogeny phi from E to E(p), we can get an attack with time complexity p one/3+o(one) Wes26 <ref:2610.21488#pg1,p^{1/3+o(1>.

Priya: But the paper seems to be showing that this smoothness isn't just a lucky guess; it's mathematically constrained.

Nadia: That’s what they are doing. The thesis of the "Smoothness of Shortest Isogenies to Frobenius Conjugates" paper is proving that delta E is smooth.

Elias: They’re arguing that this smoothness is inherent in the structure of these curves, and because they've proven it, they're affirming Wesolowski’s attack on the supersingular endomorphism ring problem as unconditional.

Nadia: That sounds like a big deal for cryptography if it holds up under real scrutiny.

Elias: It does because if this smoothness is proven to be true, then the path-finding attacks aren't just heuristics anymore; they are reliable.

Priya: So, what’s the actual claim they are making about delta E ? Is it saying every single one of these shortest degrees is smooth?

Nadia: Not every single one, but they establish bounds.

Elias: They use number-theoretic arguments involving Brandt operators and primitive connection isogenies to show upper and lower bounds for the largest prime factor P+(delta E).

Priya: What are those bounds looking like in terms of the size of p? Is it staying small or getting bigger as p gets larger?

Elias: The upper bound proof, which uses propositions like Proposition three point six and Lemma two point four, leads to the conclusion that the probability Pr(P+(delta E) B) is bounded by c two rho(u) times a logarithm of p <ref:2610.21488#pg3>.

Nadia: And they pair that up with a lower bound derived from quaternionic pairs estimates, Cp(m, n), which counts ordered pairs of distinct primitive connection isogenies <ref:2610.21488#pg3>.

Priya: That lower bound gives us something much stronger, right? What’s the actual relationship they establish there?

Elias: They get a lower bound where Pr(P+(delta E) B) is greater than or equal to c one rho(u) times (p) cubed <ref:2610.21488#pg3>.

Nadia: So they compare the upper bound, which is like B c two rho(u) p, against this lower bound, which is roughly proportional to rho(u) (p) cubed <ref:2610.21488#pg2>.

Elias: That comparison establishes the heuristic of Wesolowski in Section six <ref:2610.21488#pg3,the heuristic of Wesolowski in Section 6>.

Priya: That means that for any fixed B, there’s a guaranteed success probability because the lower bound is higher than the upper bound for certain ranges of p.

Paper summary: Nadia: Precisely. It confirms that Wesolowski's p one/3+o(one) attack on the supersingular endomorphism ring problem is unconditional <ref:2610.21488#pg1,Wesolowski's $p^{1/3+o(1)}$ attack on the supersingular endomorphism>.

Elias: That’s a significant result because it solidifies the security reduction for things like SQIsign and its variants.

Priya: So, what does this mean for someone who just listens to radio about cryptography? It means the complexity barrier they're trying to build against is actually weaker than we thought if this paper is right.

Nadia: It means the security of those systems isn't as strong as people assumed when Wesolowski first set that p one/3+o(one) threshold <ref:2610.21488#pg1,p^{1/3+o(1>.

Elias: The whole point of this paper, "Smoothness of Shortest Isogenies to Frobenius Conjugates," is showing that the distribution of these isogeny degrees is constrained in a way that confirms the attack's viability.

Priya: So, it's not just a theoretical result about numbers; it’s confirming how often these specific mathematical objects behave, which dictates how many steps an attacker actually needs.

Nadia: It’s about making sure that when you try to find those short isogenies to the Frobenius conjugate, you don't run into a wall where they are all too complicated for an attack.

Elias: The authors explicitly mention their methodology relies on relating the average mass of primitive Brandt–Hurwitz type isogenies A BHp(n) to a term involving tau(D), where D equals 4mn - t squared <ref:2610.21488#pg3>.

Priya: That sounds very specific, so what does that average mass tell us about the structure of these isogenies?

Nadia: It tells us how often these connections occur in the space of supersingular curves, and they use Proposition three point six and Lemma two point four to show that this average mass is bounded by three sqrt p n/two pi (4pn) + two <ref:2610.21488#pg3>.

Elias: That leads them directly to the conclusion that Pr(P+(delta E) B) is bounded by c two rho(u) p <ref:2610.21488#pg2>.

Nadia: And when they combine that with the lower bound from the quaternionic pairs estimate, they get that result where Pr(P+(delta E) B) is greater than or equal to c one rho(u) (p) cubed <ref:2610.21488#pg1>.

Priya: So it’s showing a gap between what you *expect* to find and what you *actually* find, and that gap is large enough for the attack to work.

Nadia: Exactly. The paper shows that for every fixed zero B, there is a range of primes where this happens, confirming the unconditional nature of Wesolowski’s p one/3+o(one) attack <ref:2610.21488#pg3>.

Elias: To wrap up, the title "Smoothness of Shortest Isogenies to Frobenius Conjugates" is a very direct description of what they proved: the smoothness property of delta E.

Priya: It confirms that for supersingular curves, there are enough smooth isogenies available to make Wesolowski's attack work reliably.

Nadia: That’s the implication. It’s not that the problem is easy; it’s that the search space for these short paths isn't sparse enough to hide a successful attack when you use those specific number-theoretic tools.

Conclusion: Nadia: So we've seen how they proved that delta E is smooth and what that means for Wesolowski's attack on supersingular endomorphism rings.

Elias: That was the main thrust of the paper, showing that this smoothness is actually a structural fact about these curves.

Priya: What does it mean in plain language for someone who isn't deep in number theory?

Nadia: It means that when you're looking for those shortest paths to the Frobenius conjugate, there are enough smooth options available to make an attack reliable.

Elias: Exactly. They established bounds where the probability of finding a B-smooth isogeny is bounded above and below by terms involving rho(u) and logarithms of p.

Priya: So, what's the actual impact on cryptography? Is this just academic math?

Nadia: It’s not just academic. It confirms that Wesolowski’s attack with time complexity p one/3+o(one) is unconditional <ref:2610.21488#pg1>.

Elias: That means the security reduction for things like SQIsign and its variants holds up even without those auxiliary assumptions they might have thought were needed.

Priya: If it's unconditional, that’s a big deal for how we trust these systems in practice.

Nadia: It’s about making sure the mathematical tools we use to assess security actually match the reality of how these objects behave.

Elias: They used quaternionic pair estimates to get that lower bound, which is what really solidifies the claim that this isn't just a lucky observation.

Priya: So, if we take it all together, they are saying the structure of these curves guarantees enough smooth paths exist for Wesolowski's attack to work reliably.

Nadia: That’s the simple version of it. They proved delta E is smooth because they showed there’s a guaranteed minimum density for those smooth isogenies.

Elias: And that density calculation, that's what confirms the feasibility of the path-finding approach for breaking these problems.

Priya: So, this paper provides a concrete reason why we can trust the complexity estimates Wesolowski made years ago.

Nadia: It gives us the mathematical foundation to assert that p one/3+o(one) attack is indeed possible and unconditional <ref:2610.21488#pg1>.

YI OUYANG, WEI WEI, ZHENG XU

School of Mathematical Sciences, University of Science and Technology of China · Hefei National Laboratory, University of Science and Technology of China

math.NT, cs.CR

Submitted: 2026-10-15

Updated: 2026-10-15

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

The gist: The gist: The smoothness of shortest isogenies to Frobenius conjugates, denoted by δE, has been proven to be smooth, which unconditionally validates Wesolowski’s p1/3+o(1) attack on the

Key concepts

$\delta_E$
This represents the smallest possible degree of an isogeny connecting a supersingular elliptic curve $E$ to its Frobenius conjugate $E^{(p)}$. Finding this minimum degree is crucial because it dictates how efficiently one can perform computations related to the curve's structure.
$B$-smoothness
A number is $B$-smooth if all of its prime factors are less than or equal to a bound $B$. The paper investigates the probability that $\delta_E$ has this property, which relates to how often the shortest isogeny degree has small prime factors.
Wesolowski's Attack
This refers to a polynomial-time attack strategy against the supersingular endomorphism ring problem. It uses isogeny path finding techniques to potentially find a nontrivial endomorphism in polynomial time, which is vital for breaking certain cryptographic schemes.
Dickman-de Bruijn function $\rho$
This mathematical function describes the distribution of smooth integers. The paper uses it to estimate the probability that $\delta_E$ is $B$-smooth, providing bounds on its largest prime factor $P^+(\delta_E)$.

Summary

The gist: The smoothness of shortest isogenies to Frobenius conjugates, denoted by δE, has been proven to be smooth, which unconditionally validates Wesolowski’s p1/3+o(1) attack on the supersingular endomorphism ring problem.

Background and Motivation

Isogeny-based cryptography relies on the arithmetic of elliptic curves and quaternion algebras. The security of schemes like SQIsign can be reduced to the hardness of the supersingular endomorphism ring problem, which Wesolowski established a polynomial-time reduction between and allowed cryptanalytic attacks through isogeny path finding. Prior to Wesolowski's work, classical and quantum algorithms for the general supersingular isogeny path-finding problem had time complexities Oe(p1/2) [DG16] and Oe(p1/4) [BJS14]. The analysis focuses on how often δE is B-smooth, which relates to the largest prime factor P+(δE). The analysis leverages results concerning smooth numbers and the Dickman-de Bruijn function ρ, which describes the distribution of smooth integers. Lemma 2.1 provides a uniform estimate for counting B-smooth integers in a specific range related to N0 = (p/2)1/3. Furthermore, Proposition 2.3 gives the class-number formula for imaginary quadratic orders, relating h(D) and w(D) to pDπL(1, χD).

Proof of Smoothness and Heuristic Validation

The main result is Theorem 1.1, which establishes bounds on the largest prime factor P+(δE). The proof proceeds by relating the probability PrP+(δE) ≤ B to the average mass of primitive Brandt–Hurwitz type isogenies A BHp(n). This average mass is shown to be bounded by a term involving τ(D), where D = 4mn − t squared. The upper bound proof uses Proposition 3.6 and Lemma 2.4 to show that A BHp(n) ≤ 3√pn/2π log(4pn) + 2. This leads to the conclusion that PrP+(δE) ≤ B ≤ c2ρ(u) log p.

Lower Bound and Cryptanalytic Implication

The lower bound is derived using the quaternionic pairs estimate, Cp(m, n), which counts ordered pairs of distinct primitive connection isogenies. The counting argument involves associating an integer triple (m, n, t) with each pair and bounding the number of such triples by estimating Cp t(m, n; [M]). By combining these bounds with the class number formula and the local-global correspondence, a lower bound is established: PrP+(δE) ≤ B ≥ c1ρ(u) (log p)3. This result implies that Wesolowski’s heuristic W is true, as log ρ(u) + log c1 − 3 log log p ≤ log PrP+(δE) < B ≤ log ρ(u) + log c2 + log log p.

Probabilistic Consequences

The analysis extends to a higher success probability for the attack. By considering the set A≤(X,B) which includes all isogenies of degree at most X, the paper shows that E[S≤E] ≥ aλρ(u) log p. This implies that Pr(A) ≥ Cε ρ(u) log p. This demonstrates that the success probability of the Frobenius-claw event is at least Cε ρ(u) log p, which is strictly larger than the bound derived from only considering minimal degree connecting isogenies.

Conclusion

The paper concludes by proving that for every fixed 0 0 such that PrP+(δE) ≤ B ≥ c1ρ(u) (log p)3. This result confirms the unconditional nature of Wesolowski’s p1/3+o(1) attack on the supersingular endomorphism ring problem. The smoothness of shortest isogenies to Frobenius conjugates is a crucial element in affirming this security result.

--- Page 1 ---

SMOOTHNESS OF SHORTEST ISOGENIES TO FROBENIUS CONJUGATES

YI OUYANG1,2, WEI WEI1 AND ZHENG XU2

Abstract. Let E be chosen uniformly from the geometric isomorphism classes of supersingular elliptic curves over Fp and δE be the minimum degree of isogenies from E to its Frobenius conjugate E(p). We prove the smoothness of δE and hence affirm Wesolowski’s p1/3+o(1) attack on the supersingular endomorphism ring problem is unconditional.

  1. Introduction

Isogeny-based cryptography forms a distinctive family of post-quantum constructions grounded in the arithmetic of elliptic curves and quaternion algebras. The landscape of isogeny-based cryptography shifted dramatically after Castryck and Decru, Maino et al., and Robert discovered polynomial-time attacks against SIDH and SIKE [CD23, MMP+23, Rob23]. These attacks leveraged the auxiliary torsion-point information exposed by SIDH and, crucially, demonstrated the power of higher-dimensional isogeny techniques. Following the polynomial time cryptanalytic breakthroughs against SIDH[Rob23], new constructions have branched into two primary research threads. The first seeks to protect sensitive information using new masking strategies or alternative representations, yielding M-SIDH and MD-SIDH [FMP23], as well as binSIDH and terSIDH constructed from artificial orientations [BF23]. The second reuses higher-dimensional isogeny techniques to build constructive cryptographic primitives. Examples include the trapdoor-based encryption schemes FESTA and QFESTA [BMP23, NO24], and the unknown-degree isogeny encryption scheme POKE [´ BM25]. SQIsign, first introduced in 2020, attracted substantial attention due to its compact signatures [DKL+20]. A series of subsequent variants — SQIsignHD [DLRW24], SQIsign2DWest [BDD+24], SQIsign2D-East [NOC+24], SQIsign2D2 [XLZO25], and SQIsign2DPush [NO26]—employ higher-dimensional isogeny representations to improve performance and reinforce security guarantees. Collectively, these developments highlight the need for rigorous analysis of the underlying computational problems in supersingular isogeny cryptography. Under their respective security models and auxiliary assumptions, the security of SQIsign and SQIsign variants can be reduced to the hardness of the supersingular endomorphism ring problem. Wesolowski established polynomial-time reductions between this problem and the supersingular isogeny path-finding problem [Wes22], allowing cryptanalytic attacks on the underlying hardness assumption to be approached through isogeny path finding. Find a nontrivial endomorphism is important since then. Prior to the work of Wesolowski [Wes26], the best-known classical and quantum algorithms for the general supersingular isogeny path-finding problem had time complexities Oe(p1/2) [DG16] and Oe(p1/4) [BJS14].

--- Page 2 ---

YI OUYANG1,2, WEI WEI1 AND ZHENG XU2

For a supersingular elliptic curve E in characteristic p, let E(p) denote its Frobenius conjugate, and δE the least isogeny degree from E to E(p):

δE:= min 0̸=φ∈Hom(E,E(p)) deg φ.

[AOV26a] tells that δE ≤ ⌊ p2/3⌋, and [Wes26] uses this establish a p1/3+o(1) attack.

However, in isogeny-based cryptography, isogenies of smooth degree are particularly amenable to efficient computation, since they can be represented and evaluated as compositions of low-degree isogenies [Feo17, Wes26]. For an isogeny of a large prime degree N, given a generator of its kernel, the square-root V´elu formulas allow its codomain to be computed and the isogeny to be evaluated at a point using Oe(√N) field operations [V´el71, BFLS20]. This naturally leads to a finer arithmetic question concerning the prime factors of δE: how often is δE B-smooth, or equivalently, how is its largest prime factor P+(δE) distributed?

Improvements for AI systems

  1. textbfIncreased Security Against Isogeny Attacks via Unconditional Guarantees: The improved system can provide an unconditional justification for Wesolowski’s attack on the supersingular endomorphism ring problem by proving that the p 1/3+o(1) attack no longer relies on this heuristic assumption and admits an unconditional justification. This allows for a stronger security proof against cryptanalytic efforts targeting SQIsign variants, as stated in Section 6.1 of the paper (Corollary 6.1).

  2. textbfAdaptive Attack Parameter Selection: The system can optimize its attack by exploiting non-minimal connecting isogenies instead of solely relying on the minimal degree isogeny, shifting from a success probability based on P+(δE) ≤ B to one based on ∃ φ: E → E(p): P+(deg(φ)) ≤ B and deg(φ) ≤ B p squared 1/3. This broadens the scope of successful cryptanalytic events, as detailed in Section 6.2.

  3. textbfEnhanced Signature Scheme Design: The system can leverage the derived bounds to design new isogeny-based cryptographic primitives with stronger security guarantees by directly utilizing the proven upper bound for the total mass of primitive Brandt–Hurwitz type isogenies, which is given by A BH p(n) = 1/2 h(-4pn) w(-4pn) + 1(p n≡3 mod 4) h(-pn) w(-pn) (Equation 3.14).

  4. textbfHigher Success Probability Estimation: The system can calculate a tighter lower bound for the probability of finding a short isogeny by using the derived formula E[S ≤ E] ≥ aγ squared ρ(v) (log p) 3 to establish that PrP+(δE) ≤ B = E[1P +δE≤B] ≥ ESE − EPE ≥ 1/2 ESE, which is then related to the lower bound PrP+(δE) ≤ B ≥ c1 ρ(u) (log p) 3 (Equation 5.37).

  5. textbfExplicit Bound Derivation: The system can derive explicit upper bounds on the number of isogeny pairs for a fixed degree by applying Lemma 5.6, yielding Cp(m, n) ≤ 17280 n squared 1 + log(2n) (Equation 5.28), providing a concrete measure for the complexity of isogeny search algorithms related to the problem.

Related papers