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).

  • $\begingroup$ Such a vector may not even exist at all. $\endgroup$
    – fkraiem
    Mar 12, 2015 at 8:28
  • $\begingroup$ But if $\{g_1,\dots,g_n\}$ is a generating subset of $g$, see this. $\endgroup$
    – fkraiem
    Mar 12, 2015 at 8:41

1 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.

  • $\begingroup$ Is this also true if the group is not cyclic? In this case, the $g_i$ produced by your reduction would all be in the subgroup of g, while this might not be true for uniformly generated elements. $\endgroup$
    – RandomGuy
    Mar 12, 2015 at 5:46
  • $\begingroup$ @RandomGuy: if group order is prime, then it is always cyclic. Otherwise, you have a good point: that would mean that I would need to omit the 'perhaps we can handle it if the group order is composite' statement at the end, or at least, qualify it. $\endgroup$
    – poncho
    Mar 12, 2015 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.