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

  • 1
    $\begingroup$ This looks like a small subgroup confinement attack. If you know $k = k_1 \mod r_1, k=k_2 \mod r_2, ... , k = k_n \mod r_n$, then by the Chinese remainder theorem, you need enough $r_i$ such that $\prod r_i > q$, the order of your finite group. But the fact that you have the same $k$ each time makes me think this isn't applicable. $\endgroup$
    – user47922
    Jun 7 '17 at 2:04
  • $\begingroup$ In other words, if you know $b_1^{k_1} = g_1 \mod r_1, b_2^{k_2} = g_2 \mod r_2, ...$, where the $r_i$ are factors of $q-1$ where $q$ is the order of the group, I can compute $k$ from the $k_i$ and $r_i$. Is that what you're asking? $\endgroup$
    – user47922
    Jun 7 '17 at 2:10
  • $\begingroup$ This is not what I am asking. Anyway, thank you for additional information. $\endgroup$
    – Rikeijin
    Jun 7 '17 at 2:11
  • $\begingroup$ Okay, got it! :) $\endgroup$
    – user47922
    Jun 7 '17 at 2:12

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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