Question

J'ai vu des exigences concurrentes dans les définitions des fonctions unidirectionnelles. À savoir

$$ Undernset {x, r} { mathbb {p}} big (f (b (f (x), r)) = f (x) big) = o (n ^ {- c}) $ $ et $$ Undernset {x} { mathbb {e}} Left [ Undernset {r} { mathbb {p}} big (f (b (f (x), r)) = f (x ) big) droite] = o (n ^ {- c}) $$

où $ x in {0,1 } ^ n $ et $ r = text {poly} (n) $. $ B $ est considéré comme un algorithme randomisé et $ r $ sont les bits aléatoires qu'il utilise.
Maintenant, je sais que pour la construction de générateurs pseudo-aléatoires à partir de permutations unidirectionnelles, l'une de ces définitions fera l'affaire, mais est-ce la même chose pour la construction des fonctions générales unidirectionnelles? Y a-t-il des cas que je devrais savoir où ces définitions ne sont pas interchangeables?

Edit: D'accord, voici ma propre explication pour expliquer pourquoi ces expressions sont égales. Si nous remplaçons le désordre entier $ f (b (f (x), r)) = f (x) $ par l'indicateur variable aléatoire $ p (x, r) $, alors nous pouvons écrire: $$ begin {Split} Undernset {x} { mathbb {e}} Left [ Undernset {r} { mathbb {p}} big (p (x, r) = 1 big) droite] & = Undernset {x } { mathbb {e}} Left [ Undernset {r} { mathbb {e}} Left [p (x, r) droite] droite] & = Undernset {x, r} {{ mathbb {e}} gauche [p (x, r) droite] & = Undernset {x, r} { mathbb {p}} big (p (x, r) = 1 big) ,. end {Split} $$

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top