Random Self-reducibility in Discrete Log 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.


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)$.


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}$.


How did they reach this conclusion?
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?)
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)