Paper 2026/364

SPRINT: New Isogeny Proofs of Knowledge and Isogeny-Based Signatures

Shai Levin, Chalmers University of Technology, University of Gothenburg

Marzio Mula, Universität der Bundeswehr München

Robi Pedersen, Technical University of Denmark

Daniel Slamanig, Universität der Bundeswehr München

Sebastian A. Spindler, Universität der Bundeswehr München

Abstract

Zero-knowledge proofs of knowledge are a fundamental building block in many isogeny-based cryptographic protocols, such as signature schemes based on identification-to-signature transformations, or multi-party ceremonies that avoid a trusted setup, in particular for generating supersingular elliptic curves with unknown endomorphism rings. In this paper, we construct SPRINT, an efficient polynomial IOP-based proof system that encodes the radical $2$-isogeny formulas into a system of multivariate polynomials. When combined with the recent polynomial commitment scheme (PCS) DeepFold, our construction yields substantial improvements over state-of-the-art isogeny proofs of knowledge. For the SQIsign NIST-I prime $p=5 \cdot 2^{248}-1$, our implementation takes only a few milliseconds for proving and verification, with proof sizes around 80 kB. Compared to the previous state-of-the-art proof system by den Hollander, Mula, Slamanig & Spindler (PQCrypto'26), we achieve speedups ranging from $1.1\times$ to $22.7\times$ for the prover and from $4.4\times$ to $109\times$ for the verifier, while achieving proof sizes that are $1.4\times$ to $17.5\times$ smaller, across different instantiations and parameter sets. Moreover, we study the weak simulation extractability of our proof system, which we can use as a starting point for a modular construction of signatures. We show that any Fiat–Shamir compiled interactive proof with a so-called canonical simulator is weakly simulation-extractable. We expect this general result to be applicable to other proof systems and thus of independent interest. Building on SPRINT and our wSE result, we introduce a new family of signature schemes whose security solely relies on the $\ell$-isogeny path problem, a foundational problem in isogeny-based cryptography. As a concrete instantiation, we construct a signature scheme using DeepFold as the PCS. Across the different parameter sets, a prototype implementation of our scheme sees significantly faster signing times than the highly optimized NIST specification for SQIsign, at the cost of much larger signature sizes and excluding a one-time precomputation phase. When this phase is instead included with the signing time, we still get almost on-par timings. Meanwhile our signature scheme relies on weaker assumptions and is constant-time when instantiated with a suitable PCS. Even though our signatures are large, the framework offers flexibility for tradeoffs and optimizations – both within a given PCS and by switching to alternative PCS constructions. In particular, it will naturally inherit efficiency gains from future advances in plausibly post-quantum secure PCS constructions.

Note: This is the full version of the paper accepted at Asiacrypt 2026.

@misc{cryptoeprint:2026/364,
      author = {Thomas den Hollander and Shai Levin and Marzio Mula and Robi Pedersen and Daniel Slamanig and Sebastian A. Spindler},
      title = {{SPRINT}: New Isogeny Proofs of Knowledge and Isogeny-Based Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/364},
      year = {2026},
      url = {https://eprint.iacr.org/2026/364}
}