2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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)$? $\endgroup$
    – Weikeng Chen
    Jul 9, 2018 at 19:19
  • $\begingroup$ You are right, I edited the question accordingly $\endgroup$
    – oleiba
    Jul 10, 2018 at 11:14

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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