Fonction négligeable (informatique)

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.

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

Définition

Une fonction est négligeable si elle décroît plus rapidement que l'inverse de tout polynôme. Mathématiquement, $\epsilon :\mathbb {N} \to [0,1]$ est dite négligeable si $\epsilon (n)=n^{-\omega (1)}$ pour tout n à partir d'un certain rang où $\omega$ représente la domination asymptotique en notation de Landau.

Définie ainsi, la notion est relative à la classe de problèmes résolubles en temps polynomial, puisque $n^{-\omega (1)}$ représente toute fonction négligeable devant n’importe quelle fonction de la forme ${\tfrac {1}{\mathrm {poly} (n)}}$ quand n tend vers l'infini et pour $\mathrm {poly}$ 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é

La collection des fonctions négligeables pour un paramètre $n$ est notée $\operatorname {negl} (n)$. 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.

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

Sécurité sémantique

La sécurité sémantique d'un cryptosystème à clef publique (GenClefs, Chiffrer, Déchiffrer) se définit par le jeu suivant entre un adversaire ${\mathcal {A}}$ et un challenger ${\mathcal {B}}$:

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

L'avantage de l'adversaire ${\mathcal {A}}$ capture l'idée que ${\mathcal {A}}$ est meilleur que le hasard. On pose ainsi $\mathrm {Advt} _{\mathcal {A}}={\bigl |}\Pr[b'=1\mid b=1]-\Pr[b'=1\mid b=0]{\bigr |}$.

Supposons que $\mathrm {Advt} _{\mathcal {A}}$ est une fonction négligeable de $\lambda$ pour tout ${\mathcal {A}}$. En d'autres termes, si $\lambda$ 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 $\mathrm {Advt} _{\mathcal {A}}\in \operatorname {negl} (\lambda )$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.

Annexes

Bibliographie

• [Arora et Barak 2009] (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 9.2 (« Computational security, one-way functions, and pseudorandom generators. »)
• [Bellare 2002] (en) Mihir Bellare, « A Note on Negligible Functions », Journal of Cryptology, vol. 15, n^o 4,‎ 1^er septembre 2002, p. 271–284 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-002-0116-x, lire en ligne, consulté le 15 mars 2018)
• [Goldreich 2003] (en) Oded Goldreich, Foundations of cryptography : Volume 1, Basic Tools, Cambridge University Press, 2003, 392 p. (ISBN 0-521-79172-3, OCLC 45093786, lire en ligne)
• [Katz et Lindell 2014] (en) Jonathan Katz et Yehuda Lindell, Introduction to Modern Cryptography, 2nd Edition, Boca Raton, Chapman and Hall, 2014, 583 p. (ISBN 978-1-4665-7026-9, lire en ligne), « Section 3.2.1 A Definition of Security for Encryption »