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
Abstract

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).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
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
History
2022-06-29: last of 5 revisions
2021-08-06: received
See all versions
Short URL
https://ia.cr/2021/1023
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1023,
      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{https://eprint.iacr.org/2021/1023}},
      url = {https://eprint.iacr.org/2021/1023}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.