SIDH Proof of Knowledge

Luca De Feo; Samuel Dobson; Steven D.  Galbraith; Lukas Zobernig

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: 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}
}