A new adaptive attack on SIDH

Tako Boris Fouotsa, Christophe Petit

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 (Disclaimer: this result is applicable to SIDH-type schemes only, not to SIKE.) parameters in an adaptive attack setting. We suggest attack parameters for some SIDH primes and discuss some countermeasures.
Original languageEnglish
Title of host publicationTopics in Cryptology – CT-RSA 2022
Subtitle of host publicationCryptographers’ Track at the RSA Conference 2022, Virtual Event, March 1–2, 2022, Proceedings
EditorsSteven D. Galbraith
PublisherSpringer
Pages322-344
Number of pages23
Edition1
ISBN (Electronic)9783030953126
ISBN (Print)9783030953119
DOIs
Publication statusPublished - 1 Jan 2022
EventCryptographers’ Track RSA Conference - Virtual
Duration: 7 Feb 202210 Feb 2022

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume13161
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceCryptographers’ Track RSA Conference
Abbreviated titleCT-RSA
Period7/02/2210/02/22

Keywords

  • Post-quantum cryptography
  • Cryptanalysis
  • Adaptive attacks
  • SIDH

Fingerprint

Dive into the research topics of 'A new adaptive attack on SIDH'. Together they form a unique fingerprint.

Cite this