Multiple Group Action Dlogs with (out) Precomputation

摘要: Let be the action of a group of size on a set . Let be a group action dlog instance, where our goal is to compute the unknown group element from the known set elements . The Galbraith-Hess-Smart (GHS) collision finding algorithm solves the group action dlog in steps with polynomial memory. We show that group action dlogs are suitable for precomputation attacks. More precisely, for any our precomputation algorithm computes within steps a hint of space complexity , which allows to solve any group action dlog in an online phase within steps. A typical instantiation is , which gives precomputation time and space , and online time only . Moreover, we show that solving multiple group action dlog instances allows for speedups. Namely, our collision finding algorithm solves group action dlogs in steps, instead of the straight-forward steps required for running 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 does not offer a group structure. Our algorithms have direct implications for all group action based cryptosystems, such …