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 $(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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
isogenyFESTASIDHSIKE
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.