1
$\begingroup$

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

Improve this question
$\endgroup$
  • $\begingroup$ Use randomized self-reducibility. $\endgroup$ – Yuval Filmus Nov 29 '20 at 21:08
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Ido Nov 30 '20 at 9:14
  • $\begingroup$ This is the part that requires randomized self-reducibility. $\endgroup$ – Yuval Filmus Nov 30 '20 at 9:48
  • $\begingroup$ 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? $\endgroup$ – Ido Nov 30 '20 at 10:16
  • $\begingroup$ Why do you need $b_i = a_i$? Also, note that if $b_i = a_i$ then $b_i-a_i \bmod m = 0$. $\endgroup$ – Yuval Filmus Nov 30 '20 at 10:17
  • 1
    $\begingroup$ Right, that's the idea. $\endgroup$ – Yuval Filmus Nov 30 '20 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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