Paper 2023/1506

IS-CUBE: An isogeny-based compact KEM using a boxed SIDH diagram

Abstract

Isogeny-based cryptography is one of the candidates for post-quantum cryptography. One of the benefits of using isogeny-based cryptography is its compactness. In particular, a key exchange scheme SIDH allowed us to use a $4\lambda$-bit prime for the security parameter $\lambda$. Unfortunately, SIDH was broken in 2022 by some studies. After that, some isogeny-based key exchange and public key encryption schemes have been proposed; however, most of these schemes use primes whose sizes are not guaranteed as linearly related to the security parameter $\lambda$. As far as we know, the remaining schemes have not been implemented due to the computation of isogenies of high dimensional abelian varieties, or they need to use a ``weak" curve (\textit{i.e.}, a curve whose endomorphism ring is known) as the starting curve. In this study, we propose a novel compact isogeny-based key encapsulation mechanism named IS-CUBE via Kani's theorem and a $3$-dimensional SIDH diagram. A prime used in IS-CUBE is of the size of about $8\lambda$ bits, and we can use a random supersingular elliptic curve for the starting curve. The public key of IS-CUBE is about $3$ times larger than that of SIKE, and the ciphertext of IS-CUBE is about $4$ times larger than that of SIKE from theoretical estimation. In practice, compared to FESTA, the public key of IS-CUBE is slightly larger and its ciphertext is slightly smaller. The core idea of IS-CUBE comes from the hardness of some already known computational problems and a novel computational problem (the Long Isogeny with Torsion (LIT) problem), which is the problem to compute a hidden isogeny from two given supersingular elliptic curves and information of torsion points of relatively small order.