Paper 2026/193 Original: eprint.iacr.org/2026/193 ↗

On the Use of Atkin and Weber Modular Polynomials in Isogeny Proofs of Knowledge

Abstract

Zero-knowledge proofs of knowledge of isogenies constitute a key building block in the design of isogeny-based signature schemes and have numerous other practical applications. A recent line of work investigated such proofs based on generic proof systems, e.g., zk-SNARKs, along with a suitable arithmetization and in particular rank-1 constraint systems (R1CS). Cong, Lai and Levin (ACNS'23) considered proving the knowledge of an isogeny of degree $2^k$ between supersingular elliptic curves via modular polynomial relations. Recently, den Hollander et al. (CRYPTO'25) have shown that the use of canonical modular polynomials instead of the classical ones allows to improve on the number of constraints for the same types of isogenies, and further allows to extend this approach to isogenies of higher (though limited) degrees. Another recent work by Levin and Pedersen (ASIACRYPT'25) showed that switching from modular polynomials to radical isogeny formulas also leads to significant improvements (at least for the case of the prime $\ell=2$). A natural question that remained open is whether sticking with the modular polynomial-based approach, but switching to other candidates of modular polynomials, and in particular Atkin and Weber polynomials, is possible and gives improvements and flexibility. In this paper we show that the use of the Atkin modular polynomials enables the use of degrees not covered by existing works and improves the number of constraints for $\ell > 2$ by up to $27\%$, while the Weber polynomials allow up to $39\%$ sparser constraint systems than the current state of the art. As in our prior work on canonical modular polynomials, the adaption of well-known results to the Atkin and Weber modular polynomials also requires some technical work, especially when going to positive characteristic. To this end we expand and optimize our previous resultant-based methodology, resulting in much simpler proofs for our multiplicity theorems.