Paper 2021/1051

Collisions in Supersingular Isogeny Graphs and the SIDH-based Identification Protocol

Wissam Ghantous and Federico Pintore and Mattia Veroni

Abstract

The digital signatures that have been proposed so far in the setting of the Supersingular Isogeny Diffie-Hellman scheme (SIDH) were obtained by applying the Fiat-Shamir transform - and a quantum-resistant analogous, the Unruh transform - to an interactive identification protocol introduced by De Feo, Jao and Pl$\hat{\mbox{u}}$t. The security of the resulting schemes is therefore deduced from that of the base identification protocol. In this paper, we revisit the proofs that have appeared in the literature for the special soundness property of the above mentioned SIDH-based identification protocol. All such proofs consider the same extraction algorithm, which is claimed to always extract a valid witness for a statement $\statement$ when given two valid transcripts, with the same commitment and different challenges, relative to $\statement$ itself. We show that this is not always the case, with some explicit counterexamples. The general argument fails due to some special cycles in supersingular isogeny graphs. The existence of these special cycles not only enjoys a theoretical interest, but is generally relevant for the Isogeny-based Cryptography. We provide some theoretical results on their presence in supersingular isogeny graphs, and discuss the relevance of the obtained results for some known cryptographic applications.