Renforcer une attaque donnée sur un journal discret

Nov 30 2020

J'essaie de prouver l'affirmation suivante:

Laisser $(G,*)$ être un groupe cyclique de taille $m$ avec générateur $g$. Supposons qu'il existe un adversaire$A'$ de taille $T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$, pour certains $T$, tel que $$\mathbb{P}_{b\gets G}\left[A'(b)=\log_{g}(b)\right]>\frac{1}{2}.$$ Montrer qu'il existe un adversaire $A$ de taille $T$ tel que $$\mathbb{P}_{b\gets G}\left[A(b)=\log_{g}(b)\right]>\frac{3}{4}.$$ Supposons une multiplication sur $G$ a besoin $O(1)$ circuit.

Comment puis-je prouver cette affirmation? Intuitivement, depuis$A$ est plus grand que $A'$ à propos $O(\log m)$, la construction doit être basée sur la division récursive du problème en deux, comme dans la recherche binaire. Cependant, je ne peux pas penser à un moyen intelligent de le faire ...

Réponses

1 YuvalFilmus Nov 30 2020 at 04:24

Supposons que nous ayons une garantie plus forte: $A'$ est un algorithme aléatoire, et pour chaque $b$, $\Pr[A'(b) = \log_g b] > 1/2$, sur le caractère aléatoire de l'algorithme . Dans ce cas, vous construiriez$A$ en exécutant $A'$ plusieurs fois, et en vérifiant chaque sortie jusqu'à ce que vous en ayez une qui satisfait $g^{A'(b)} = b$.

Supposons maintenant que la garantie soit $\Pr_b[A'(b) = \log_g b] > 1/2$. Vous souhaitez en quelque sorte obtenir des "échantillons indépendants" de$A'(b)$. Vous pouvez accomplir cela en utilisant l'auto-réductibilité aléatoire. Je vous laisse le remplir puisque c'est votre exercice. L'algorithme résultant est aléatoire, mais en choisissant le caractère aléatoire optimal, vous obtenez un algorithme déterministe (mais non uniforme) avec les mêmes garanties.