Welcome to the resource topic for 2023/507
Title:
Low Memory Attacks on Small Key CSIDH
Authors: Jesús-Javier Chi-Domínguez, Andre Esser, Sabrina Kunzweiler, Alexander May
Abstract: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.
ePrint: https://eprint.iacr.org/2023/507
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .