Усиление данной атаки по дискретному бревну

Question

Я пытаюсь доказать следующее утверждение:

Позволять $(G,*)$ быть циклической группой размера $m$ с генератором $g$. Предположим, что существует противник$A'$ размера $T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$, для некоторых $T$, так что $$\mathbb{P}_{b\gets G}\left[A'(b)=\log_{g}(b)\right]>\frac{1}{2}.$$ Покажите, что есть противник $A$ размера $T$ такой, что $$\mathbb{P}_{b\gets G}\left[A(b)=\log_{g}(b)\right]>\frac{3}{4}.$$ Предположим, что умножение более $G$ требует $O(1)$ цепь.

Как я могу доказать это утверждение? Интуитивно, поскольку$A$ больше чем $A'$ примерно $O(\log m)$, конструкция должна быть основана на рекурсивном делении задачи на половинки, как в бинарном поиске. Однако я не могу придумать какой-либо умный способ сделать это ...

Answer 1

Предположим, у нас была более сильная гарантия: $A'$ является рандомизированным алгоритмом, и для каждого $b$, $\Pr[A'(b) = \log_g b] > 1/2$, по случайности алгоритма . В этом случае вы должны построить$A$ бегом $A'$ несколько раз и проверяя каждый вывод, пока не получите тот, который удовлетворяет $g^{A'(b)} = b$.

Теперь предположим, что гарантия $\Pr_b[A'(b) = \log_g b] > 1/2$. Вы бы хотели как-то получить «независимые образцы»$A'(b)$. Вы можете добиться этого, используя рандомизированную самовосстановление. Я позволю вам заполнить его, так как это ваше упражнение. Результирующий алгоритм является случайным, но, выбирая оптимальную случайность, вы получаете детерминированный (но неоднородный) алгоритм с теми же гарантиями.