이산 로그에 대한 주어진 공격 강화
다음 주장을 증명하려고합니다.
허락하다 $(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)$, 구성은 이진 검색에서와 같이 문제를 반복적으로 절반으로 나누는 것을 기반으로해야합니다. 그러나 나는 그것을 할 영리한 방법을 생각할 수 없습니다 ...
답변
더 강력한 보증이 있다고 가정합니다. $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)$. 무작위 자기 축소를 사용하여이를 달성 할 수 있습니다. 운동 이니까 기입 해 드리겠습니다. 결과 알고리즘은 무작위 화되지만 최적의 무작위성을 선택하면 동일한 보장을 가진 결정 론적 (그러나 비 균일) 알고리즘을 얻을 수 있습니다.