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.


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

  • $\begingroup$ Very informative answer, thanks for the help! $\endgroup$
    – Gabi G
    Commented Dec 1, 2020 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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