1
$\begingroup$

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

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

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.

$\endgroup$
  • $\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 '15 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 '15 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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