Paper 2021/1023
SIDH Proof of Knowledge
Luca De Feo and Samuel Dobson and Steven D. Galbraith and Lukas Zobernig
Abstract
We demonstrate the soundness proof for the De Feo, Jao and Plût identification scheme (the basis for SIDH signatures) contains an invalid assumption and 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. We propose a modified identification scheme fixing the issue with the De Feo, Jao and Plût scheme, and provide a proof of security of this new scheme. We also prove that a modification of this scheme allows the torsion points in the public key to be verified too. This results in a secure proof of knowledge for SIDH keys and a secure SIDH-based signature scheme. In particular, these schemes provide a non-interactive way of verifying that SIDH public keys are well formed as protection against adaptive attacks, more efficient than generic NIZKs.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Post-quantum cryptographyDiffie-Hellman key exchangesupersingular elliptic curvesisogeniesSIDHproof of knowledgepublic key verification
- Contact author(s)
- samuel dobson nz @ gmail com,s galbraith @ auckland ac nz,luca @ defeo lu,lukas zobernig @ auckland ac nz
- History
- 2023-05-11: last of 7 revisions
- 2021-08-06: received
- See all versions
- Short URL
- https://ia.cr/2021/1023
- License
-
CC BY