# Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard

Show that if the discrete log problem is $$(T,1-\epsilon)$$-hard, then it's $$(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$$-hard

Let $$G$$ be a cyclic group of size $$m$$, and let $$g \in G$$ be a generator.

We say the the discrete log problem is $$(T,\epsilon)$$-hard if for every algorithm $$A$$ of complexity at most $$T$$, it statisfies: $$P[A(a) = log_g(a)] \le \epsilon$$ when $$a$$ is chosen uniformly from $$G$$. This means that $$A$$ can give the correct value of $$log_g(a)$$ with probability $$\le \epsilon$$.

Now I assume that the discrete log problem is $$(T, 1-\epsilon)$$-hard and want to prove that it's $$(O(\frac{T}{\frac{1}{\epsilon}log\epsilon} -nlog(m)), \epsilon)\text{-hard}$$ where $$n$$ is the time to compute a group operation on $$G$$.

The complexity of $$O(nlogm)$$ it is what needed to calculate $$g^a$$ for an arbitrary $$a \in G$$, which makes me think that such thing can be used here.

I would want to assume that there is an algorithm $$A$$ of size $$K$$ that guesses the correct discrete log for an arbitrary $$a \in G$$ with probability $$> \epsilon$$.

Then, somehow use $$A$$ to solve the discrete log problem with probability $$> 1-\epsilon$$.

However, I don't really see how to do it. Maybe run $$A$$ with the input $$a \in G$$ and return the opposite answer in some way. Help would be appreciated.

Suppose that there exists an algorithm $$A$$ which runs in time $$T_A\le \frac{T}{\frac{1}{\epsilon}\log\frac{1}{\epsilon}}-n\log m$$, and $$\Pr\limits_{a\sim U(G)}\left[A(a)=\log_g a\right]\ge \epsilon$$. We want to enhance the success probability of $$A$$. The trick is to evaluate $$A$$ on different elements $$b_1,...,b_k$$ (who of course depend on the input $$a$$) whose logarithm will allow us to recover $$\log_g a$$. Define $$A'$$ as follows, given input $$a$$ pick independently $$i_1,...,i_k\in [m]$$ uniformly at random, and evaluate $$A$$ on the inputs $$ag^{i_1},...,ag^{i_k}$$. For each $$1\le j\le k$$ check whether $$A(ag^{i_j})=\log_g ag^{i_j}$$ (the verification requires $$n\log m$$ time), and if there exists $$j$$ for which the equality holds return $$A(ag^{i_j})-i_j \pmod m$$. The running time of $$A'$$ is bounded by $$k(T_A+n\log m)\le \frac{k}{\frac{1}{\epsilon}\log\frac{1}{\epsilon}}T$$. I leave it to you to show that $$ag^{i_1},...,ag^{i_k}$$ are independent and therefore we can write $$\Pr\limits_{a\sim U(G)}\left[A'(a)=\log_g(a)\right]\ge 1-(1-\epsilon)^k\ge 1-e^{-\epsilon k}\ge 1-\epsilon$$, for $$k=\frac{1}{\epsilon}\log\frac{1}{\epsilon}$$.