Paper 2023/1506

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

Tomoki Moriya, University of Birmingham
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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
isogeny-based cryptographyKani's theoremSIDHKEM
Contact author(s)
t moriya @ bham ac uk
History
2024-02-26: last of 2 revisions
2023-10-02: received
See all versions
Short URL
https://ia.cr/2023/1506
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1506,
      author = {Tomoki Moriya},
      title = {{IS}-{CUBE}: An isogeny-based compact {KEM} using a boxed {SIDH} diagram},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1506},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1506}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.