# Does knowledge of equal exponents decrease security?

Say I have a group $G$ with two different generators $g_1$ and $g_2$, where the discrete log from one to another is unknown.
Also, there are two public commitments $g_1^{r}$ and $g_2^{r}$, where it is publicly known that they are raised to the same $r$ (but unknown which $r$).

Does the latter piece of information compromise security in any way?

• But in the discrete log problem, we usually do better than brute-force, like baby-step giant-step. I think the question is how much security is reduced. So you want to make sure that the adversary cannot learn $r$ from $(g_1^r,g_2^r)$? – Weikeng Chen Jul 9 '18 at 19:19
• You are right, I edited the question accordingly – oleiba Jul 10 '18 at 11:14

This answer aims to show that the security does not decrease.

Let me explain it as a game. $\mathcal{D}$ is the challenger who asks $\mathcal{A}$ to solve a 2-hint DL problem.

$\mathcal{D}(\mathcal{G})$ samples $r$ and sends $(g_1,g_2,g_1^r,g_2^r)$ to $\mathcal{A}$.
$\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$ is supposed to answer $r$ correctly with a non-neglibigle possibility.

First, let me formalize "the discrete log from one to another is unknown".

There is a group $\mathcal{G}$ and a public generator $g_1$. $\mathcal{D}$ chooses $g_2$ as follows:

1. Samples $s\in\{0,1,...,\mathsf{ord}(\mathcal{G})\}$, where $\mathsf{ord}(\cdot)$ means the order of a group.
2. Computes $g_2=(g_1)^s$.

Then, let me introduce the basic DL game, which consists of another challenger $\mathcal{D}'$ and another adversary $\mathcal{A}'$.

$\mathcal{D}'(\mathcal{G})$ samples $r$ and sends $(g_1,g_1^r)$ to $\mathcal{A}'$.
$\mathcal{A}'(g_1,g_1^r)$ is supposed to answer $r$ correctly with a non-negligible possibility.

In groups where DL assumptions are believed to hold, a probabilistic polynomial-time $\mathcal{A}'$ cannot answer with a non-negligible possibility of getting it correct.

Now, we say $\mathcal{A}'$ is winning if it can output the correct answer with a non-negligible possibility.

So, we know there is no $\mathcal{A}'$ winning in $(\mathcal{D}',\mathcal{A}')$ game.

Now, if there is a PPT adversary $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$ that can play $(\mathcal{D},\mathcal{A})$ game with a non-negligible possibility of winning.

Then, there is a winning $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$.

We can construct a winning $\mathcal{A}'(g_1,g_1^r)$ from this winning $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$ as follows:

1. Samples $s\in\{0,1,...,\mathsf{ord}(\mathcal{G})\}$.
2. Computes $g_2=g_1^s$.
3. Computes $g_2^r=(g_1^r)^s$.
4. Outputs the answer of $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$.

Then, if $\mathcal{A}$ is winning, $\mathcal{A}'$ is also winning.
This contradicts the fact that there is not winning $\mathcal{A}'$.

So, such $\mathcal{A}$ does not exist.
In other words, there is no PPT adversary that can break your construction.

I think this answer also shows that it cannot be used to reduce the number of rounds for attacking.