QFESTA: Efficient Algorithms and Parameters for FESTA using Quaternion Algebras

Kohei Nakagawa; Hiroshi Onuki

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

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 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 -isogeny and -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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: isogeny FESTA SIDH SIKE
Contact author(s): kohei nakagawa @ ntt com
hiroshi-onuki @ g ecc u-tokyo ac jp
History: 2024-06-07: last of 4 revisions; 2023-09-25: received; See all versions
Short URL: https://ia.cr/2023/1468
License: CC BY

BibTeX

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