Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Isogeny-based Cryptography, Identification Protocol, Special Soundness, Supersingular Isogeny Graph, Digital Signature, Post-quantum Cryptography, SIDH

Date: received 13 Aug 2021

Contact author: wissam ghantous at maths ox ac uk, federico pintore at uniba it, mattia veroni at ntnu no

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2021/1051

[ Cryptology ePrint archive ]