Paper 2021/1023
SIDH Proof of Knowledge
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} }