Exhaustivité de définition formelle de la « dureté de la moyenne »

Question

Lors de la lecture d'un manuel de cryptographie, je trouve la définition d'une fonction qui est difficile à la moyenne. (Plus précisément, il est « difficile à la moyenne, mais facile avec entrée auxiliaire », mais j'omettent ce dernier pour plus de simplicité.)

Définition: Hard sur la moyenne :

$ h: \ {0,1 \} ^ * \ à \ {0,1 \} ^ * $ est difficile à la moyenne si il existe un algorithme probabiliste polynomial $ G $ tel que
pour chaque algorithme probabiliste polynomial $ A '$ chaque polynôme positif $ p (\ cdot) $, et tout suffisamment large $ n $' s, Pr $ [A '(X_n) = h (X_n)] <\ frac { 1} {p (n)} $

où $ X_n:. = G (1 ^ n) $ est une variable aléatoire affecté à la sortie de $ G $

Ma question est pourquoi la déclaration de l'existence d'un algorithme qualifié G est suffisante?

En d'autres termes, pourquoi la définition ci-dessus donne une définition formelle de la « dureté de la moyenne » au lieu de la définition suivante, qui est plus intuitive (?) À comprendre et plus stricte. Pourquoi la définition ci-dessus suffisante?

(Maintenant, je pense à ce problème pourrait se produire lorsque $ G $ a seulement nombre polynôme de sorties possibles, mais le cas échéant, nous allons remplacer « pour tout $ G $ » avec « pour tout G $, ce qui $ de façon exponentielle beaucoup possible sorties dans la définition suivante.)

(forte?) Def: Hard sur la moyenne :

$ h: \ {0,1 \} ^ * \ à \ {0,1 \} ^ * $ est difficile sur la moyenne si pour tout probabiliste polynomial algorithme $ G $ et pour chaque algorithme probabiliste polynomial $ A '$ chaque polynôme positif $ p (\ cdot) $, et toutes suffisamment grande $ n $' s, Pr $ [A '(X_n) = h (X_n)] <\ frac {1} {p (n)} $

où $ X_n:. = G (1 ^ n) $ est une variable aléatoire affecté à la sortie de $ G $

Une autre question est que si une définition suivante plus simple est équivalente à la définition originale ou non?

(simple) Def: Hard sur la moyenne :

$ h: \ {0,1 \} ^ * \ à \ {0,1 \} ^ * $ est difficile à la moyenne si pour chaque algorithme probabiliste polynomial $ A '$ chaque polynôme positif $ p ( \ cdot) $, et tout suffisamment large $ n 's, Pr $ [A' $ (U_n) = h (U_n)] <\ frac {1} {p (n)} $

où $ U_n $ est une variable aléatoire uniformément répartie sur $ \ {0,1 \} ^ n $.

Answer 1

Hard en moyenne est parfois définie comme dans votre troisième (simple) définition: une fonction $ h $ est difficile en moyenne si sur une entrée uniformément aléatoire, sa sortie ne peut pas être prédite par un ppt avec plus d'une probabilité négligeable. La première définition englobe également la situation dans laquelle la distribution d'entrée « correcte » est différent. Par exemple, considérons la fonction $$ h (xy) = \ begin {cas} H (x) et y = 0, \\ 0 & y \ neq 0, \ end {cas} $$ où $ | x | = | Y | $ et $ H $ est une fonction dure en moyenne (sous la simple définition). La fonction $ h $ n'est pas difficile, en moyenne, dans la définition de simple, mais il est difficile, en moyenne, la définition plus compliquée. Je ne sais pas pourquoi nous devrions nous intéresser à ces fonctions, mais il y a probablement une raison. Vous devrez continuer à lire et à réfléchir lorsque la définition plus complexe est nécessaire.

En ce qui concerne votre deuxième définition, il est beaucoup trop forte. Considérons par exemple ce qui se passe si $ G $ génère toujours la chaîne zéro. Vous capturez encore quelque chose - la fonction arrêt sera toujours difficile - mais il n'y a pas de notion de « moyenne ». Vous avez en effet prévu dans votre commentaire (si elle ne s'applique vraiment dans le cadre non uniforme), mais la notion qui en résulte est encore sans doute trop forte.

La notion de dure en moyenne est sorti d'une tentative de preuve de la sécurité d'une certaine idée. Bien qu'il est en effet destiné à saisir un sens intuitif de la dureté en moyenne, les détails ont été déterminés à partir de certains arguments qui les ont utilisés, d'une certaine construction qui les a obtenus; ils ne sont pas arbitraires. Ces notions ont été jugées utiles, ce qui est la raison pour laquelle ils continuent d'être utilisés. Votre idée suggérée pourrait être utile aussi bien, mais le fardeau de la preuve est sur vous.