Paper 2023/1468
QFESTA: Efficient Algorithms and Parameters for FESTA using Quaternion Algebras
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 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.
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
- 2023-11-07: last of 2 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}, note = {\url{https://eprint.iacr.org/2023/1468}}, url = {https://eprint.iacr.org/2023/1468} }