# Is this discrete log generalization a well known cryptographic assumption?

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

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

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.

• 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. Mar 12, 2015 at 5:46
• @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. Mar 12, 2015 at 14:31
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}