Paper 2023/1092

The wrong use of FESTA trapdoor functions leads to an adaptive attack

Tomoki Moriya, University of Birmingham
Hiroshi Onuki, University of Tokyo

Isogeny-based cryptography is one of the candidates for post-quantum cryptography. In 2023, Kani's theorem breaks an isogeny-based scheme SIDH, which was considered a promising post-quantum scheme. Though Kani's theorem damaged isogeny-based cryptography, some researchers have been trying to dig into the applications of this theorem. A FESTA trapdoor function is an isogeny-based trapdoor function that is one trial to apply Kani's theorem to cryptography. This paper claims that there is an adaptive attack for a FESTA-based scheme if this scheme does not check the correctness of the input matrix. Our attack cannot be adapted to IND-CCA PKE schemes named FESTA proposed in the FESTA original paper so far. In this paper, we provide an adaptive attack for a FESTA trapdoor function using a specific oracle, and it reveals the secret key of the function. This oracle may be constructed if the FESTA trapdoor function is used in the wrong way (\textit{i.e.,} without the checking process of the input matrix). As an example, we explain that our attack can be adapted to a possible PKE scheme based on a FESTA trapdoor function in the wrong way.

Available format(s)
Attacks and cryptanalysis
Publication info
isogeny-based cryptographyFESTAadaptive attackKani's theorem
Contact author(s)
t moriya @ bham ac uk
onuki @ mist i u-tokyo ac jp
2024-02-01: last of 5 revisions
2023-07-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tomoki Moriya and Hiroshi Onuki},
      title = {The wrong use of FESTA trapdoor functions leads to an adaptive attack},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1092},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.