Wzmocnienie danego ataku na dyskretny dziennik

Nov 30 2020

Próbuję udowodnić następujące twierdzenie:

Pozwolić $(G,*)$ być cykliczną grupą wielkości $m$ z generatorem $g$. Załóżmy, że istnieje jakiś przeciwnik$A'$ wielkościowy $T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$, dla niektórych $T$, takie że $$\mathbb{P}_{b\gets G}\left[A'(b)=\log_{g}(b)\right]>\frac{1}{2}.$$ Pokaż, że istnieje przeciwnik $A$ wielkościowy $T$ takie że $$\mathbb{P}_{b\gets G}\left[A(b)=\log_{g}(b)\right]>\frac{3}{4}.$$ Załóżmy, że mnożenie się skończyło $G$ wymaga $O(1)$ obwód.

Jak mogę to udowodnić? Intuicyjnie, ponieważ$A$ jest większe niż $A'$ za około $O(\log m)$konstrukcja powinna opierać się na rekurencyjnym podzieleniu problemu na połowy, tak jak w przypadku wyszukiwania binarnego. Jednak nie mogę wymyślić żadnego sprytnego sposobu, aby to zrobić ...

Odpowiedzi

1 YuvalFilmus Nov 30 2020 at 04:24

Załóżmy, że mamy silniejszą gwarancję: $A'$ jest algorytmem losowym i dla każdego $b$, $\Pr[A'(b) = \log_g b] > 1/2$, nad losowością algorytmu . W takim przypadku możesz skonstruować$A$ biegiem $A'$ kilka razy i sprawdzając każde wyjście, aż uzyskasz takie, które będzie satysfakcjonujące $g^{A'(b)} = b$.

Teraz przypuśćmy, że jest to gwarancja $\Pr_b[A'(b) = \log_g b] > 1/2$. Chciałbyś w jakiś sposób uzyskać „niezależne sample”$A'(b)$. Możesz to osiągnąć za pomocą losowej samodredukowalności. Pozwolę ci to wypełnić, ponieważ to twoje ćwiczenie. Wynikowy algorytm jest losowy, ale wybierając optymalną losowość, otrzymujesz deterministyczny (ale niejednorodny) algorytm z tymi samymi gwarancjami.