Paper 2021/1051

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

Wissam Ghantous, Shuichi Katsumata, Federico Pintore, and Mattia Veroni

Abstract

The digital signature schemes 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 analog, the Unruh transform - to an interactive identification protocol introduced by De Feo, Jao and Plû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 aforementioned SIDH-based identification protocol. All such proofs consider the same extraction algorithm, which is claimed to always extract the witness for a statement x when given two valid transcripts, with the same commitment and different challenges, relative to x itself. We show that this is not always the case, with some explicit counterexamples. The general argument fails due to some special cycles, which we call collisions, in supersingular isogeny graphs. We provide some theoretical results on their existence, and discuss their impact on the security of the SIDH-based digital signatures. Relying on the Generalised Riemann Hypothesis, we also introduce an alternative extractor for which we rigorously prove the special soundness property.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Isogeny-based CryptographyIdentification ProtocolSpecial SoundnessSupersingular Isogeny GraphDigital SignaturePost-quantum CryptographySIDH
Contact author(s)
wissam ghantous @ maths ox ac uk
federico pintore @ uniba it
mattia veroni @ ntnu no
History
2022-03-29: revised
2021-08-16: received
See all versions
Short URL
https://ia.cr/2021/1051
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1051,
      author = {Wissam Ghantous and Shuichi Katsumata and Federico Pintore and Mattia Veroni},
      title = {Collisions in Supersingular Isogeny Graphs and the {SIDH}-based Identification Protocol},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1051},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1051}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.