You are looking at a specific version 20210824:000701 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.