# Strengthening a given attack on discrete log

I am trying to prove the following claim:

Let $$(G,*)$$ be a cyclic group of size $$m$$ with generator $$g$$. Assume there exists some adversary $$A'$$ of size $$T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$$, for some $$T$$, such that $$\mathbb{P}_{b\gets G}\left[A'(b)=\log_{g}(b)\right]>\frac{1}{2}.$$ Show that there exists an adversary $$A$$ of size $$T$$ such that $$\mathbb{P}_{b\gets G}\left[A(b)=\log_{g}(b)\right]>\frac{3}{4}.$$ Assume multiplication over $$G$$ requires $$O(1)$$ circuit.

How can I prove this claim? Intuitively, since $$A$$ is bigger than $$A'$$ in about $$O(\log m)$$, the construction should be based on dividing the problem into halfs recursively, as in binary search. However, I can't think of any clever way to do that...

• Use randomized self-reducibility. – Yuval Filmus Nov 29 '20 at 21:08

Suppose that we had a stronger guarantee: $$A'$$ is a randomized algorithm, and for every $$b$$, $$\Pr[A'(b) = \log_g b] > 1/2$$, over the randomness of the algorithm. In that case, you would construct $$A$$ by running $$A'$$ several times, and checking each output until you get one that satisfies $$g^{A'(b)} = b$$.

Now suppose that the guarantee is $$\Pr_b[A'(b) = \log_g b] > 1/2$$. You would like to somehow get "independent samples" of $$A'(b)$$. You can accomplish that using randomized self-reducibility. I'll let you fill that out since it's your exercise. The resulting algorithm is randomized, but by choosing the optimal randomness, you get a deterministic (but non-uniform) algorithm with the same guarantees.

• Hey, thanks for your help! I have a small question. You suggested sampling $A'(b)$ several times to get a better estimation for $\log_g (b)$. However, we assume $b$ is chosen uniformly over $G$ and $A'$ returns some value when given $b$. So if $A'$ is a deterministic algorithm, it would always return the same outputs for the same inputs. In other words, if we keep feeding it with some fixed $b$ we have sampled, it will keep giving us the same result over and over... I'm a little confused here – Ido Nov 30 '20 at 9:14
• This is the part that requires randomized self-reducibility. – Yuval Filmus Nov 30 '20 at 9:48
• I eventually used the following method. I sample $a_1,a_2, a_3 \gets \mathbb{Z}_m$, and calculate $g_i \gets X\cdot g^{a_i}$ for each. Later I calculate $b_i \gets A'(g_i)$. After that I search for some $i$ such that $b_i =a_i$, and if I find one, I return $b_i-a_i \mod m$. Does it look ok? – Ido Nov 30 '20 at 10:16
• Why do you need $b_i = a_i$? Also, note that if $b_i = a_i$ then $b_i-a_i \bmod m = 0$. – Yuval Filmus Nov 30 '20 at 10:17
• Right, that's the idea. – Yuval Filmus Nov 30 '20 at 12:42