Fortalecimento de um determinado ataque em log discreto

Question

Estou tentando provar a seguinte afirmação:

Deixei $(G,*)$ ser um grupo cíclico de tamanho $m$ com gerador $g$. Suponha que exista algum adversário$A'$ de tamanho $T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$, para alguns $T$, de tal modo que $$\mathbb{P}_{b\gets G}\left[A'(b)=\log_{g}(b)\right]>\frac{1}{2}.$$ Mostre que existe um adversário $A$ de tamanho $T$ de tal modo que $$\mathbb{P}_{b\gets G}\left[A(b)=\log_{g}(b)\right]>\frac{3}{4}.$$ Suponha que a multiplicação $G$ requer $O(1)$ o circuito.

Como posso provar essa afirmação? Intuitivamente, desde$A$ é maior do que $A'$ em cerca de $O(\log m)$, a construção deve ser baseada na divisão do problema em metades recursivamente, como na pesquisa binária. No entanto, não consigo pensar em nenhuma maneira inteligente de fazer isso ...

Answer 1

Suponha que tenhamos uma garantia mais forte: $A'$ é um algoritmo aleatório, e para cada $b$, $\Pr[A'(b) = \log_g b] > 1/2$, sobre a aleatoriedade do algoritmo . Nesse caso, você construiria$A$ Correndo $A'$ várias vezes, e verificando cada saída até obter uma que satisfaça $g^{A'(b)} = b$.

Agora suponha que a garantia seja $\Pr_b[A'(b) = \log_g b] > 1/2$. Você gostaria de obter de alguma forma "amostras independentes" de$A'(b)$. Você pode fazer isso usando autorredutibilidade aleatória. Vou deixar você preencher isso, pois é o seu exercício. O algoritmo resultante é aleatório, mas ao escolher a aleatoriedade ideal, você obtém um algoritmo determinístico (mas não uniforme) com as mesmas garantias.