Paper 2026/1166

$\Delta$-SQIsign: A New Isogeny-Based Signature Scheme Using Degree Challenges

Abstract

Isogeny-based cryptography is a kind of cryptography whose security relies on the computational hardness of the isogeny problem. This field is gaining attention as a promising candidate for post-quantum cryptography. Among the notable schemes within this category is SQIsign, a signature schemes that has been submitted to the NIST Post-Quantum Cryptography Standardization competition. In this paper, we introduce a new isogeny-based signature scheme, $\Delta$-SQIsign, which represents a significant departure from existing isogeny-based signatures including SQIsign. The key distinction in our scheme lies in its use of the degree of isogeny as a challenge within the underlying $\Sigma$-protocol. Then, the prover outputs an isogeny of the given degree as a response. To construct such a scheme, we introduce a new algorithm, called $\Delta$-KLPT, which is a variant of GeneralizedKLPT. Similar to GeneralizedKLPT, our algorithm outputs an ideal equivalent to a given ideal with a fixed norm; however, under certain conditions, it can produce an ideal of smaller norm than GeneralizedKLPT.

Note: Following the publication of the original version of this paper on ePrint, Riccardo Invernizzi, Frederik Vercauteren, Matthias Kerkhofs, Thomas Decru, Valerio Ardizio, and Wouter Castryck contacted us regarding a security issue. To investigate the concern, we withdrew the original submission. We later confirmed that the issue can be avoided and therefore resubmitted the paper under the same title.