L'inverse d'une fonction unidirectionnelle $ f $ est-il réductible à un prédicat $ b $ implique que $ b $ est un bit dur pour $ f $?

Question

Je travaille avec cette définition pour les fonctions à sens unique:

Nous appelons $ f $ a (forte) une fonction unidirectionnelle si

1. il est calculable en temps polynomial
2. Pour tout algorithme randomisé à temps polynomial $ b $ et toute constante $ c $ $$ mathbb {p} big (f (b (f (x))) = f (x) big) = o (n ^ {- c}) $$ où $ x in {0,1 } ^ n. $

Et cette définition pour les bits durs:

Soit $ f: {0,1 } ^ n rightarrow {0,1 } ^ k $ et $ b: {0,1 } ^ n rightarrow {0,1 } $ be calculable en temps polynomial. Nous disons que $ f $ est une fonction à sens unique avec un bit de noyau dur $ b $ si, pour tous les algorithmes randomisés $ b $ et toutes les constantes $ c $, $$ mathbb {p} (b (f (x) ) = b (x)) = frac {1} {2} + o (n ^ {- c}) ,. $$

Et je me demande si, si $ f $ est à sens unique et que la recherche de $ x $ de $ f (x) $ est du temps polynomial réductible à la recherche de $ b (x) $ de $ f (x) $, $ b $ doit être dur. Une façon de structurer cet argument est comme ça: $$ text {Rechercher $ x $ réduit à la recherche $ b (x) $} implique big (f text {est unidirection hard-core} big) $$ ou par contrapositif: $$ text {trouver $ x $ réduit à la recherche $ b (x) $} implique big (b text {n'est pas du core dur} f text {n'est pas unidirectionnel} big) $$

Supposons donc que la recherche de $ x $ réduit à la recherche de $ b (x) $ et $ b $ n'est pas difficile. Ensuite, la stratégie évidente consiste à passer par la réduction, mais au lieu de calculer $ b (x) $ de manière déterministe, nous faisons une bonne supposition en utilisant un algorithme $ b $ qui doit exister car $ b $ n'est pas dur. Puisque nous avons une chance non négligeable de réussir de deviner correctement $ b (x) $, nous nous retrouvons avec une chance non négligeable de deviner correctement $ x $ et donc $ f $ n'est pas à sens unique.
Mais il y a un point ici où le problème arrive. Alors que nous connaissons la probabilité de calculer correctement un seul $ b (x) $ pour un $ x $ aléatoire, je n'ai aucune poignée sur la probabilité de succès pour une séquence d'appels $ b (x_i) $ où le $ x_i $ sont arbitrairement corrélés.