Welcome to the resource topic for 2024/564
Title:
Multiple Group Action Dlogs with(out) Precomputation
Authors: Alexander May, Massimo Ostuzzi
Abstract:Let \star: G \times X \rightarrow X be the action of a group G of size N=|G| on a set X. Let y = g \star x \in X be a group action dlog instance, where our goal is to compute the unknown group element g \in G from the known set elements x,y \in X.
The Galbraith-Hess-Smart (GHS) collision finding algorithm solves the group action dlog in N^{\frac 1 2} steps with polynomial memory.
We show that group action dlogs are suitable for precomputation attacks. More precisely, for any s,t our precomputation algorithm computes within st steps a hint of space complexity s, which allows to solve any group action dlog in an online phase within t steps. A typical instantiation is s=t=N^{\frac 1 3}, which gives precomputation time N^{\frac 2 3} and space N^{\frac 1 3}, and online time only N^{\frac 1 3}.
Moreover, we show that solving multiple group action dlog instances y_1, \ldots , y_m allows for speedups. Namely, our collision finding algorithm solves m group action dlogs in \sqrt{m}N^{\frac 1 2} steps, instead of the straight-forward mN^{\frac 1 2} steps required for running m times GHS.
Interestingly, our multi instance algorithm (with precomputation) can be seen as a special case of our precomputation algorithm.
Our multiple instance approach can be freely combined with our precomputations, allowing for a variety of tradeoffs.
Technically, our precomputation and multiple instance group action dlog attacks are adaptations of the techniques from the standard dlog setting in abelian groups. While such an adaptation seems natural, it is per se unclear which techniques transfer from the dlog to the more restricted group dlog setting, for which X does not offer a group structure.
Our algorithms have direct implications for all group action based cryptosystems, such as CSIDH and its variants. We provide experimental evidence that our techniques work well in the CSIDH setting.
ePrint: https://eprint.iacr.org/2024/564
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 .