IACR News item: 03 October 2023
Tomoki Moriya
ePrint Report
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 forgave 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 rest 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 its starting curve is a random supersingular elliptic curve. The core idea of IS-CUBE comes from the hardness of some already known computational problems and the novel computational problem (the Computational Long Isogeny with Torsion (CLIT) problem), which is the problem to compute a hidden isogeny from given two supersingular elliptic curves and information of torsion points of a relatively small order. From our PoC implementation of IS-CUBE via \textsf{sagemath}, it takes about $4.34$ sec for the public key generation, $0.61$ sec for the encapsulation, and $17.13$ sec for the decapsulation if $\lambda = 128$.
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 rest 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 its starting curve is a random supersingular elliptic curve. The core idea of IS-CUBE comes from the hardness of some already known computational problems and the novel computational problem (the Computational Long Isogeny with Torsion (CLIT) problem), which is the problem to compute a hidden isogeny from given two supersingular elliptic curves and information of torsion points of a relatively small order. From our PoC implementation of IS-CUBE via \textsf{sagemath}, it takes about $4.34$ sec for the public key generation, $0.61$ sec for the encapsulation, and $17.13$ sec for the decapsulation if $\lambda = 128$.
Additional news items may be found on the IACR news page.