Paper 2024/564
Multiple Group Action Dlogs with(out) Precomputation
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 GalbraithHessSmart (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 straightforward $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 general group action 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.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Keywords
 group actionsCSIDHpreprocessingmultiinstance dlogsrandom walks
 Contact author(s)

alex may @ rub de
massimo ostuzzi @ rub de  History
 20240524: last of 3 revisions
 20240411: received
 See all versions
 Short URL
 https://ia.cr/2024/564
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/564, author = {Alexander May and Massimo Ostuzzi}, title = {Multiple Group Action Dlogs with(out) Precomputation}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/564}, year = {2024}, url = {https://eprint.iacr.org/2024/564} }