Paper 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.

Note: To appear at CT-RSA 2022

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Post-quantum cryptographycryptanalysisadaptive attacksSIDH
Contact author(s)
takoboris fouotsa @ uniroma3 it
christophe f petit @ gmail com
History
2021-12-05: revised
2021-10-05: received
See all versions
Short URL
https://ia.cr/2021/1322
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1322,
      author = {Tako Boris Fouotsa and Christophe Petit},
      title = {A New Adaptive Attack on {SIDH}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1322},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1322}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.