QFESTA: Efficient Algorithms and Parameters for FESTA using Quaternion Algebras

Kohei, Nakagawa, Hiroshi, Onuki

QFESTA: Efficient Algorithms and Parameters for FESTA using Quaternion Algebras

情報処理学会

抄録

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-degreeisogeny computations and is not expected to be efficient. 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 INDCCA2 security in QROM by applying Fujisaki-Okamoto transform. Our protocol only requires (2, 2)-isogeny and 3-isogeny computations. This leads to a significant reduction in computational costs. In addition, our protocol has much smaller data sizes of public key and ciphertext than the original FESTA.