Paper 2023/507

Low Memory Attacks on Small Key CSIDH

Jesús-Javier Chi-Domínguez, Technology Innovation Institute
Andre Esser, Technology Innovation Institute
Sabrina Kunzweiler, Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest Research Centre
Alexander May, Ruhr University Bochum

Despite recent breakthrough results in attacking SIDH, the CSIDH protocol remains a secure post-quantum key exchange protocol with appealing properties. However, for obtaining efficient CSIDH instantiations one has to resort to small secret keys. In this work, we provide novel methods to analyze small key CSIDH, thereby introducing the representation method ---that has been successfully applied for attacking small secret keys in code- and lattice-based schemes--- also to the isogeny-based world. We use the recently introduced Restricted Effective Group Actions ($\mathsf{REGA}$) to illustrate the analogy between CSIDH and Diffie-Hellman key exchange. This framework allows us to introduce a $\mathsf{REGA}\text{-}\mathsf{DLOG}$ problem as a level of abstraction to computing isogenies between elliptic curves, analogous to the classic discrete logarithm problem. This in turn allows us to study $\mathsf{REGA}\text{-}\mathsf{DLOG}$ with ternary key spaces such as $\{-1, 0, 1\}^n, \{0,1,2\}^n$ and $\{-2,0,2\}^n$, which lead to especially efficient, recently proposed CSIDH instantiations. The best classic attack on these key spaces is a Meet-in-the-Middle algorithm that runs in time $3^{0.5 n}$, using also $3^{0.5 n}$ memory. We first show that $\mathsf{REGA}\text{-}\mathsf{DLOG}$ with ternary key spaces $\{0,1,2\}^n$ or $\{-2,0,2\}^n$ can be reduced to the ternary key space $\{-1,0,1\}^n$. We further provide a heuristic time-memory tradeoff for $\mathsf{REGA}\text{-}\mathsf{DLOG}$ with keyspace $\{-1,0,1\}^n$ based on Parallel Collision Search with memory requirement $M$ that under standard heuristics runs in time $3^{0.75 n}/M^{0.5}$ for all $M \leq 3^{n/2}$. We then use the representation technique to heuristically improve to $3^{0.675n}/M^{0.5}$ for all $M \leq 3^{0.22 n}$, and further provide more efficient time-memory tradeoffs for all $M \leq 3^{n/2}$. Although we focus in this work on $\mathsf{REGA}\text{-}\mathsf{DLOG}$ with ternary key spaces for showing its efficacy in providing attractive time-memory tradeoffs, we also show how to use our framework to analyze larger key spaces $\{-m, \ldots, m\}^n$ with $m = 2,3$.

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. ACNS 2023
IsogenyTime-Memory Trade-offRepresentation Technique
Contact author(s)
jesus dominguez @ tii ae
andre r esser @ gmail com
sabrina kunzweiler @ math u-bordeaux fr
alex may @ rub de
2023-04-10: approved
2023-04-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jesús-Javier Chi-Domínguez and Andre Esser and Sabrina Kunzweiler and Alexander May},
      title = {Low Memory Attacks on Small Key CSIDH},
      howpublished = {Cryptology ePrint Archive, Paper 2023/507},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.