Paper 2021/1023

SIDH Proof of Knowledge

Luca De Feo, IBM Research Europe
Samuel Dobson, University of Auckland
Steven D. Galbraith, University of Auckland
Lukas Zobernig, University of Auckland

We show that the soundness proof for the De Feo-Jao-Plut identification scheme (the basis for supersingular isogeny Diffie-Hellman (SIDH) signatures) contains an invalid assumption, and we provide a counterexample for this assumption---thus showing the proof of soundness is invalid. As this proof was repeated in a number of works by various authors, multiple pieces of literature are affected by this result. Due to the importance of being able to prove knowledge of an SIDH key (for example, to prevent adaptive attacks), soundness is a vital property. Surprisingly, the problem of proving correctness of an isogeny turns out to be considerably more difficult than was perhaps anticipated. The main result of this paper is a sigma protocol to prove that an SIDH public key (including the torsion points in the public key) is correctly formed. Our scheme also avoids the SIDH identification scheme soundness issue raised by Ghantous, Pintore and Veroni. In particular, our protocol provides a non-interactive way of verifying that SIDH public keys are well-formed as protection against adaptive attacks, leading to an SIDH-based non-interactive key exchange (NIKE).

Available format(s)
Public-key cryptography
Publication info
Post-quantum cryptography Diffie-Hellman key exchange supersingular elliptic curves isogenies SIDH proof of knowledge public key verification
Contact author(s)
luca @ defeo lu
samuel dobson nz @ gmail com
s galbraith @ auckland ac nz
lukas zobernig @ auckland ac nz
2022-06-29: last of 5 revisions
2021-08-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Luca De Feo and Samuel Dobson and Steven D.  Galbraith and Lukas Zobernig},
      title = {SIDH Proof of Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1023},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.