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 one-third the size of the original FESTA.

Note: We received feedback from Andrea Basso, Tako Boris Fouotsa, Giacomo Pope, and Luciano Maino, indicating that our proposed parameter does not meet the expected security level. We have some countermeasures and plan to make corrections in the near future.

Available format(s)
Public-key cryptography
Publication info
Contact author(s)
kohei nakagawa @ ntt com
hiroshi-onuki @ g ecc u-tokyo ac jp
2023-11-07: last of 2 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.