International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

QFESTA: Efficient Algorithms and Parameters for FESTA using Quaternion Algebras

Authors:
Kohei Nakagawa , NTT Social Informatics Laboratories
Hiroshi Onuki , The University of Tokyo
Download:
DOI: 10.1007/978-3-031-68388-6_4 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: 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 parameters for that protocol, but the parameters require 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 algebras 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.
BibTeX
@inproceedings{crypto-2024-34179,
  title={QFESTA: Efficient Algorithms and Parameters for FESTA using Quaternion Algebras},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68388-6_4},
  author={Kohei Nakagawa and Hiroshi Onuki},
  year=2024
}