How can we determine if two discrete logarithms are equal?

Let $p$ be a prime number, and let $g_{1},g_{2},...,g_{n}$ be $n$ generator of $Z^{*}_{p}$. We have a list $y_{1},y_{2},\dotsc,y_{n}$ of elements in $Z^{*}_{p}$ such that for every $i\in \lbrace1,2,\dotsc,n \rbrace$ we have $y_{i}=g_{i}^{x_{i}} \bmod p$ for some number $x_{i}$ (but we don't know $x_{i}$). I am trying to find an algorithm to determine all pairs $(y_{i},y_{j})$, $i\neq j$ such that $x_{i}=x_{j}$.

-

If you know what powers of one generator results in the other generators then the problem is easy. Please clarify your question to indicate whether this is the case or not. – Barack Obama Jan 11 at 2:06

1 Answer

This problem is equivalent to the decisional Diffie-Hellman problem, and hence your problem is intractable (assuming, of course, that the group is well chosen).

Here's how we can use an Oracle that can solve the above problem to solve the DDH problem:

• In the DDH problem, we're given values $g, g^x, g^y, g^z$, and we're asked whether $xy = z$.

• We call the Oracle with the following instance: $n=2$, $g_1 = g$, $g_2 = g^x$, $y_1 = g^y$, $y_2 = g^z$.

• The Oracle will return that $x_1 = x_2$ is a matching pair iff, for that same $w$, $g_1^w = y_1$ and $g_2^w = y_2$, that is, if $g^w = g^y$ and $g^{wx} = g^z$, which is to say, if $g^{xy} = g^z$

It's also obvious how to solve your problem with an Oracle that solves the DDH problem (using $n (n-1)/2$ calls to the Oracle).

-
I believe there are some groups in which the decisional DH problem is easy, but the computational DH problem is hard. These are useful for some unusual protocols. – CodesInChaos Jan 9 at 19:51

1
@CodesInChaos: yes, there are such groups; however, the group $Z^{*}_{p}$ is not one of them. – poncho Jan 9 at 19:55
{"extraction_info": {"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": 29, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.929008960723877, "perplexity_flag": "head"}