Verstärkung eines bestimmten Angriffs auf diskrete Protokolle

Question

Ich versuche folgende Behauptung zu beweisen:

Lassen $(G,*)$ eine zyklische Gruppe von Größe sein $m$ mit Generator $g$. Angenommen, es gibt einen Gegner$A'$ von Größe $T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$, für einige $T$, so dass $$\mathbb{P}_{b\gets G}\left[A'(b)=\log_{g}(b)\right]>\frac{1}{2}.$$ Zeigen Sie, dass es einen Gegner gibt $A$ von Größe $T$ so dass $$\mathbb{P}_{b\gets G}\left[A(b)=\log_{g}(b)\right]>\frac{3}{4}.$$ Nehmen Sie die Multiplikation an $G$ erfordert $O(1)$ Schaltkreis.

Wie kann ich diese Behauptung beweisen? Intuitiv seit$A$ ist größer als $A'$ in ungefähr $O(\log m)$Die Konstruktion sollte darauf basieren, das Problem wie bei der binären Suche rekursiv in zwei Hälften zu teilen. Ich kann mir jedoch keinen cleveren Weg vorstellen, das zu tun ...

Answer 1

Angenommen, wir hätten eine stärkere Garantie: $A'$ ist ein randomisierter Algorithmus und für jeden $b$, $\Pr[A'(b) = \log_g b] > 1/2$, Über die Zufälligkeit des Algorithmus . In diesem Fall würden Sie konstruieren$A$ durch Laufen $A'$ mehrmals und überprüfen Sie jede Ausgabe, bis Sie eine erhalten, die zufriedenstellend ist $g^{A'(b)} = b$.

Nehmen wir nun an, dass die Garantie ist $\Pr_b[A'(b) = \log_g b] > 1/2$. Sie möchten irgendwie "unabhängige Proben" von bekommen$A'(b)$. Sie können dies durch zufällige Selbstreduzierbarkeit erreichen. Ich lasse Sie das ausfüllen, da es Ihre Übung ist. Der resultierende Algorithmus ist randomisiert, aber durch Auswahl der optimalen Zufälligkeit erhalten Sie einen deterministischen (aber nicht einheitlichen) Algorithmus mit denselben Garantien.