Fonction négligeable (informatique)

fonction dont l'utilisation de ressources est négligeable devant une référence

Une fonction négligeable en informatique fondamentale, surtout en cryptographie et en complexité algorithmique, est une notion qui permet de caractériser (souvent pour en ignorer les effets) une fonction mathématique dont la contribution est faible par rapport à une référence. Il s'agit d'une notion asymptotique, qui ne prend son sens que lorsqu'on s'intéresse au comportement des fonctions sur de très grandes entrées. Enfin, une fonction n'est négligeable que vis-à-vis d'une classe de complexité donnée ; dans l'extrême majorité des cas, la classe implicitement considérée est polynomiale[1].

Définition et premières propriétés

modifier

Définition

modifier

Une fonction est négligeable si elle décroît plus rapidement que l'inverse de tout polynôme. Mathématiquement,   est dite négligeable si   pour tout n à partir d'un certain rang où   représente la domination asymptotique en notation de Landau[2].

Définie ainsi, la notion est relative à la classe de problèmes résolubles en temps polynomial, puisque   représente toute fonction négligeable devant n’importe quelle fonction de la forme   quand n tend vers l'infini et pour   un polynôme à une variable. C'est presque toujours par rapport à cette classe qu'on se réfère en pratique, considérant qu'il s'agit d'un bon modèle des capacités des calculateurs réels.

Compositionnalité

modifier

La collection des fonctions négligeables pour un paramètre   est notée  . C'est une collection stable par les opérations arithmétiques (addition, multiplication) et par composition. En d'autres termes, aucun algorithme terminant en un temps polynomial ne permet de construire une fonction non négligeable à partir seulement d'appels à une fonction négligeable[3].

Cette propriété, à rapprocher des infinitésimaux, permet de construire des arguments hybrides : une succession de jeux dans lesquels l'avantage de l'adversaire est une fonction négligeable (d'un paramètre de sécurité), et qui trace un pont progressif entre une situation idéale et une situation réelle. L'accumulation de ces avantages négligeables, par compositionnalité, reste négligeable.

Exemple

modifier

Sécurité sémantique

modifier

La sécurité sémantique d'un cryptosystème à clef publique (GenClefs, Chiffrer, Déchiffrer) se définit par le jeu suivant[4] entre un adversaire   et un challenger  :

  1.   obtient les informations publiées par  , notamment sa clef publique de chiffrement pk (issue de GenClefs à partir d'un paramètre de sécurité  ).
  2.   tire un bit aléatoire b ∈ {0,1}
  3.   choisir un message M qu'il transmet à  
  4. Si  ,   répond par un message aléatoire. En revanche, si  , alors   transmet à   le chiffré de  .
  5.   doit deviner s'il a reçu le chiffré de   ou non.   retourne donc un bit b’ qui vaut 1 dans le premier cas, et 0 dans le second.

L'avantage de l'adversaire   capture l'idée que   est meilleur que le hasard. On pose ainsi  .

Supposons que   est une fonction négligeable de   pour tout  . En d'autres termes, si   est assez grand, aucun algorithme terminant en temps polynomial ne peut (en participant à ce jeu) distinguer un chiffré d'un message aléatoire. A fortiori, identifier le contenu d'un message chiffré est hors de portée de tout algorithme réel, et on parle donc de sécurité « sémantique » calculatoire.

Notons toutefois que prouver  n'est en général démontrable que sous des hypothèses (peut-être optimistes) de difficulté calculatoire, et que l'utilisation de cryptosystèmes d'autre manières (par exemple en autorisant un adversaire à faire des requêtes de déchiffrement) n'est pas garantie sûre par la seule sécurité sémantique.

De manière symétrique, s'il existe un adversaire possédant un avantage non négligeable dans ce jeu, alors le cryptosystème n'est pas sûr.

Notes et références

modifier

Annexes

modifier

Bibliographie

modifier