Dans quelles circonstances les fonctions unidirectionnelles sont-elles réductibles à leurs bits durs?
-
05-11-2019 - |
Question
J'ai vu des affirmations concurrentes sur les prédicats durs. D'une part, il y a la définition de base
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}) ,. $$
Mais j'ai aussi lu la déclaration
Nous voulons que le problème de trouver $ x $ soit réductible, en temps polynomial, au problème de la recherche de $ b (x) $, de sorte que trouver $ b (x) $ est tout aussi difficile que de trouver tout $ x $. Dans ce cas, $ b $ est appelé un bit dur pour $ f $.
Comment ces exigences sont-elles liées? L'un est-il plus fort que l'autre? Ou s'impliquent-ils?
Pas de solution correcte