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

Question

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.

Answer 1

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