Is this discrete log generalization a well known cryptographic assumption?

Question

Assume you have a finite group $\mathbb{G}$ and an integer $n$. Given $g_1,\dots,g_n,t$ chosen uniformly from $\mathbb{G}$, consider the problem of finding a vector $(a_1,\dots,a_n)\in \mathbb{Z}^n$ such that $$g_1^{a_1}\cdot \ldots \cdot g_n^{a_n} = t $$

Is there any class of groups where the problem is known to be computationally hard? Does the computational assumption have a well established name?

For $n=1$, the problem is equivalent to discrete log, and in general it is easier than discrete log (meaning that solving DL immediately gives a solver for this problem).

Answer 1

Actually, that problem is exactly equivalent to the standard DLOG problem (assuming that you know the group order, and that it is prime).

Here's the reduction: suppose that we have an Oracle that can solve your problem with nontrivial probability. Then, given a value $g$ and $h$, we can find $x$ with $g^x = h$ with nontrivial probability by:

• Create random values $r_1, r_2, ..., r_n$ and $s$ between 0 and the group order (except that $s$ cannot be 0).

• Compute $g_i = g^{r_i}$ and $t = h^s$. Note that the values $g_i$ and $t$ are uniformly distributed (except that $t$ is not the identity).

• Give the values $g_i$ and $t$ to your Oracle, which computes the values $a_i$ with nontrivial probability.

• $x = s^{-1}\ \sum\ a_i r_i$

The only reason we needed to assume that the group order was prime was to be precise in the assumption that the elements be chosen randomly; if we relax that restriction on $t$, we can handle composite group orders as well.