How many pairs of ${b_i}^k \equiv g_i\pmod p$ are enough to solve discrete logarithm problem?

Question

On the group of multiplication modulo large prime $p$ of $m$ bits

Given $$ b_1^k=g_1 \;\text {mod}\;p$$ $$ b_2^k=g_2 \;\text{mod}\;p$$ $$ b_3^k=g_3 \;\text{mod}\;p$$ $$ \vdots $$ $$ b_n^k=g_n \;\text{mod}\;p$$

How many pairs are enough to computationally solve $k$ of this discrete logarithm problem? I have this question because if we erroneously use the random number generator in Elgamal encryption The masking key may have relation, e.g. the masking key is the square of previous one modulo $p$. We can decrypt the ciphertext easily, but we may still not know the private key of Bob (the receiver.), but we can know many pairs of relation like equations above. Are the pairs let we solve the private key of Bob(receiver)?

Answer 1

Having multiple sets $b_i^k = g_i$ with a common solution $k$ do not help you recover $k$; it cannot make the problem much easier than if you had the simple equation $b^k = g$.

Here's the proof; suppose that there was an efficient way to recover $k$ given a $n$ different $b_i^k = g_i$ equations.

Then, we can efficiently solve the simple equation $b^k = g$ by doing the following:

• We select $n$ random values $r_1, ..., r_n$

• We compute:

$$b_i = b^{r_i}$$

$$g_i = g^{r_i}$$

• We have our $n$ equations, as $b_i^k = (b^{r_i})^k = (b^k)^{r_i} = g^{r_i} = g_i$, so we use the efficient way to recover $k$ given $n$ equations.

We then know the solution $k$ to the original equation, and the only extra time we took was to the time select $n$ random values and to compute $2n$ modular exponentiations.