2
$\begingroup$

I understand what Random Self-reducibility means and how it is used in the Discrete Log. What is not clear is

  1. how does it show that DL is hard in the average case.

The probability of success of an imperfect DL black box is $p(n)$ (for an $n$-bit string, and $p$ is a polynomial). So, in order to get a correct DL for an input $y$ is $1/p(n)$.

  1. Does this mean that finding the DL of a single $y$ can be done in polynomial time? (just run the algorithm $n*poly(n)$ which is still a polynomial!)

Afterward, in a lecture the professor, went over describing that the probability of succeeding every time is $$\left(1-\frac{1}{p(n)}\right)^np(n)$$ and that this is less than $e^{-n}$.

  1. How did they reach this conclusion?
  2. If the conclusion is correct, does this mean that the machine is successful every time with negligible probability (so finding a DL of every is negligible?)
$\endgroup$
  • 2
    $\begingroup$ Could you provide a link for the definition of your Random Self-reducibility $\endgroup$ – kelalaka Jan 8 at 10:06
0
$\begingroup$

I understand what Random Self-reducibility means and how it is used in the Discrete Log. What is not clear is how does it show that DL is hard in the average case.

Actually, Random Self-reducibility does not show that DL is hard in any case. What it does show that if there exists a hard DL instance, then random DL instances are hard.

Remember, the "Random Self-reducibility" property is that we can take an arbitrary instance of the problem $g^x = h$, find $x$, and turn it into a random instance $r_1^y = r_2$, find $y$, and if we can solve the random instance, we can go back and solve our original problem.

How it shows that average instance is hard is by showing the converse; if the random instance had a nontrivial probability of being easy, then we can solve any arbitrary instance (by randomly transforming our arbitrary instance a number of times, and if we happen to hit an easy instance, which we have a good probability of doing, we get to solve the original problem).

All this formalism (which is what is tripping you up) is just expressing this concept in mathematical terms (as opposed to the verbal description I used).

Of course, if you try to do formalism, it is important to get the formulae right.

The probability of success of an imperfect DL black box is $p(n)$ (for an $n$-bit string, and $p$ is a polynomial). So, in order to get a correct DL for an input $y$ is $1/p(n)$.

Actually, the probability would be $1/p(n)$; remember, probabilities are restricted to the range $[0,1]$

Afterward, in a lecture the professor, went over describing that the probability of succeeding every time is

Actually, if the attacker is attempting to do this, he doesn't have a succeed every time; all he needs to do is succeed once. A single success (that is, a random reduction into an instance that allows him to solve the DL problem) will tell time the answer to the DL problem he is actually interested in.

$\left(1-\frac{1}{p(n)}\right)^np(n)$

That might be the probability that the attacker will need to perform precisely $n+1$ random reductions before hitting on an answer, but if so, I'm pretty sure you garbled that formula (as well as apparently using $n$ with two different meanings, the size of the DL problem, and the number of random reductions the attacker tries)

$\endgroup$
  • $\begingroup$ this was very very helpful, can I ask you if you could explain a bit more the very last formula? how do we prove that DL is hard on average? $\endgroup$ – graphtheory92 Jan 12 at 9:35
0
$\begingroup$

1. how does it show that DL is hard in the average case.

We can show this with the following reduction;

Suppose that we have an algorithm $A$ that solves the DL for the half of the inputs $y$. That is, $A(y)$ return $x$ as $y = g^x$ for only half of the possible input values $y$.

Now to solve the general case $y$, select a random $r$ and see $A$ can find the DL of $g^rh$.

It is clear that the $A$ has $1/2$ chance of returning the correct value. If you try in polynomial time, it will likely work for at least one $r$.

Once we get $A(g^rh)=y$, then we can deduce that $h = g^{y-r}$, and thus this solves the DLOG of $y$.

This is a reduction from the average case to the general case. The reverse is obvious and this implies DL is hard in the average case.

2. Does this mean that finding the DL of a single y can be done in polynomial time?

No, it is probabilistic polynomial time.

3. How did they reach this conclusion?

Poncho corrected your result, I'll go another way.

Let repeat the process $1/p(n)$-times then, on any input $y'$, A will fail to invert with $y'$ in all these independent trials is at most

$$ (1-p(n))^{p(n)} \leq e^{-1} \leq \frac{1}{2}$$

Therefore, after $1/p(n)$ trials of $r$ it will succeed to invert some $y'$.

4. If the conclusion is correct, does this mean that the machine is successful every time with negligible probability (so finding a DL of every is negligible?)

Yes, otherwise the imperfect DL black box will be a polynomial time reduction.

$\endgroup$
  • $\begingroup$ I believe there is some error in your question. $\endgroup$ – kelalaka Jan 8 at 14:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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