Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Post-quantum cryptography, Diffie-Hellman key exchange, supersingular elliptic curves, isogenies, SIDH, proof of knowledge, public key verification

Date: received 4 Aug 2021, last revised 23 Aug 2021

Contact author: samuel dobson nz at gmail com, s galbraith at auckland ac nz, luca at defeo lu, lukas zobernig at auckland ac nz

Available format(s): PDF | BibTeX Citation

Version: 20210824:000701 (All versions of this report)

Short URL: ia.cr/2021/1023