Memperkuat serangan yang diberikan pada log diskrit

Question

Saya mencoba membuktikan klaim berikut:

Membiarkan $(G,*)$ menjadi kelompok ukuran siklik $m$ dengan generator $g$. Asumsikan ada beberapa musuh$A'$ ukuran $T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$, untuk beberapa $T$, seperti yang $$\mathbb{P}_{b\gets G}\left[A'(b)=\log_{g}(b)\right]>\frac{1}{2}.$$ Tunjukkan bahwa ada musuh $A$ ukuran $T$ seperti yang $$\mathbb{P}_{b\gets G}\left[A(b)=\log_{g}(b)\right]>\frac{3}{4}.$$ Asumsikan perkalian selesai $G$ membutuhkan $O(1)$ sirkuit.

Bagaimana saya bisa membuktikan klaim ini? Secara intuitif, sejak$A$ lebih besar dari $A'$ di sekitar $O(\log m)$, konstruksi harus didasarkan pada pembagian masalah menjadi beberapa bagian secara rekursif, seperti dalam pencarian biner. Namun, saya tidak dapat memikirkan cara cerdas untuk melakukan itu ...

Answer 1

Misalkan kita memiliki jaminan yang lebih kuat: $A'$ adalah algoritme acak, dan untuk setiap $b$, $\Pr[A'(b) = \log_g b] > 1/2$, atas keacakan algoritme . Dalam hal ini, Anda akan membangun$A$ dengan berlari $A'$ beberapa kali, dan memeriksa setiap keluaran sampai Anda mendapatkan hasil yang memuaskan $g^{A'(b)} = b$.

Sekarang anggaplah jaminan itu $\Pr_b[A'(b) = \log_g b] > 1/2$. Anda ingin mendapatkan "sampel independen" dari$A'(b)$. Anda dapat melakukannya dengan menggunakan kemampuan reduksi diri secara acak. Saya akan membiarkan Anda mengisinya karena ini adalah latihan Anda. Algoritme yang dihasilkan diacak, tetapi dengan memilih keacakan yang optimal, Anda mendapatkan algoritme deterministik (tetapi tidak seragam) dengan jaminan yang sama.