Paper 2023/1468

QFESTA: Efficient Algorithms and Parameters for FESTA using Quaternion Algebras

Kohei Nakagawa, NTT Social Informatics Laboratories
Hiroshi Onuki, The University of Tokyo

In 2023, Basso, Maino, and Pope proposed FESTA (Fast Encryption from Supersingular Torsion Attacks), an isogeny-based public-key encryption (PKE) protocol that uses the SIDH attack for decryption. In the same paper, they proposed a parameter for that protocol, but the parameter requires high-degree isogeny computations. In this paper, we introduce QFESTA (Quaternion Fast Encapsulation from Supersingular Torsion Attacks), a new variant of FESTA that works with better parameters using quaternion algebras and achieves IND-CCA security under QROM. To realize our protocol, we construct a new algorithm to compute an isogeny of non-smooth degree using quaternion algebra and the SIDH attack. Our protocol relies solely on $(2,2)$-isogeny and $3$-isogeny computations, promising a substantial reduction in computational costs. In addition, our protocol has significantly smaller data sizes for public keys and ciphertexts, approximately half size of the original FESTA.

Available format(s)
Public-key cryptography
Publication info
Contact author(s)
kohei nakagawa @ ntt com
hiroshi-onuki @ g ecc u-tokyo ac jp
2024-06-07: last of 4 revisions
2023-09-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kohei Nakagawa and Hiroshi Onuki},
      title = {{QFESTA}: Efficient Algorithms and Parameters for {FESTA} using Quaternion Algebras},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1468},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.