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

Tomoki Moriya; Hiroshi Onuki

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: isogeny-based cryptography FESTA adaptive attack Kani's theorem
Contact author(s): t moriya @ bham ac uk
onuki @ mist i u-tokyo ac jp
History: 2024-02-01: last of 5 revisions; 2023-07-13: received; See all versions
Short URL: https://ia.cr/2023/1092
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1092,
      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},
      url = {https://eprint.iacr.org/2023/1092}
}