africacrypt2025.sciencesconf.org
16th International Conference on Cryptology, Africacrypt 2025 - Sciencesconf.org
Africacrypt 2025 is organized by the ENSIAS College of Mohammed V University in Rabat with partnership of the General Directorate of Information Systems Security (DGSSI), Morocco.
![Abstract. In this paper we study supersingular elliptic curves primitively oriented by an imaginary quadratic order, where the orientation is determined by an endomorphism that factors through the Frobenius isogeny. In this way, we partly recycle one of the main features of CSIDH, namely the fact that the Frobenius orientation can be represented for free. This leads to the most efficient family of ideal-class group actions in a range where the discriminant is significantly larger than the field characteristic p. Moreover, if we orient with a non-maximal order $\mathcal{O} \subset \mathbb{Q}(\sqrt{-p})$ and we assume that it is feasible to compute the ideal-class group of the maximal order, then also the ideal-class group of 𝒪 is known and we recover the central feature of SCALLOP-like constructions.
We propose two variants of our scheme. In the first one, the orientation is by a suborder of the form $\mathbb{Z}[f\sqrt{-p}]$ for some f coprime to p, so this is similar to SCALLOP. In the second one, inspired by the work of Chenu and Smith, the orientation is by an order of the form $\mathbb{Z}[\sqrt{-dp}]$ where d is square-free and not a multiple of p. We give practical ways of generating parameters, together with a proof-of-concept SageMath implementation of both variants, which shows the effectiveness of our construction.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreibqnnsbrycfnj6lxmqemiovkeexw3n3kfjoj7vw2oybinwvn4xeym)
![Abstract. We study a new pairing, beyond the Weil and Tate pairing. The Weil pairing is a non-degenerate pairing E[m] × E[m] → μ_(m), which operates on the kernel of [m]. Similarly, when μ_(m) ⊆ 𝔽_(q)^(*), the Tate pairing is a non-degenerate pairing E[m](𝔽_(q)) × E(𝔽_(q))/[m]E(𝔽_(q)) → μ_(m), which connects the kernel and the rational cokernel of [m]. We define a pairing
⟨ ⟩_(m) : E(𝔽_(q))/[m]E(𝔽_(q)) × E(𝔽_(q))/[m]E(𝔽_(q)) → μ_(m)
on the rational cokernels of [m], filling the gap left by the Weil and Tate pairing. When E[m] ⊆ E(𝔽_(q)), this pairing is non-degenerate, and can be computed using three Tate pairings, and two discrete logarithms in μ_(m), assuming a basis for E[m]. For m = ℓ prime, this pairing allows us to study E(𝔽_(q))/[ℓ]E(𝔽_(q)) directly and to simplify the computation for a basis of E[ℓ^(k)], and more generally the Sylow ℓ-torsion. This finds natural applications in isogeny-based cryptography when computing ℓ^(k)-isogenies.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreibl542dwky563ijtb47nfbrttztnwtvnfd2k5s7hibtzsg6iv5fqa)