Cryptology ePrint Archive: Report 2021/1322

A New Adaptive Attack on SIDH

Tako Boris Fouotsa and Christophe Petit

Abstract: The SIDH key exchange is the main building block of SIKE, the only isogeny based scheme involved in the NIST standardization process. In 2016, Galbraith et al. presented an adaptive attack on SIDH. In this attack, a malicious party manipulates the torsion points in his public key in order to recover an honest party's static secret key, when having access to a key exchange oracle. In 2017, Petit designed a passive attack (which was improved by de Quehen et al. in 2020) that exploits the torsion point information available in SIDH public key to recover the secret isogeny when the endomorphism ring of the starting curve is known.

In this paper, firstly, we generalize the torsion point attacks by de Quehen et al. Secondly, we introduce a new adaptive attack vector on SIDH-type schemes. Our attack uses the access to a key exchange oracle to recover the action of the secret isogeny on larger subgroups. This leads to an unbalanced SIDH instance for which the secret isogeny can be recovered in polynomial time using the generalized torsion point attacks. Our attack is different from the GPST adaptive attack and constitutes a new cryptanalytic tool for isogeny based cryptography. This result proves that the torsion point attacks are relevant to SIDH parameters in an adaptive attack setting. We suggest attack parameters for some SIDH primes and discuss some countermeasures.

Category / Keywords: public-key cryptography / Post-quantum cryptography, cryptanalysis, adaptive attacks, SIDH

Date: received 30 Sep 2021, last revised 5 Dec 2021

Contact author: takoboris fouotsa at uniroma3 it, christophe f petit at gmail com

Available format(s): PDF | BibTeX Citation

Note: To appear at CT-RSA 2022

Version: 20211205:223436 (All versions of this report)

Short URL: ia.cr/2021/1322


[ Cryptology ePrint archive ]