Fonction négligeable
La façon formelle qu'a la cryptographie de dire « trop petit pour compter » : finalement plus petit que l'inverse de tout polynôme.
Une fonction μ(n) est négligeable si, pour tout polynôme p, elle finit par passer sous 1/p(n). 2−n est négligeable ; 1/n100 ne l'est pas. Cette notion sous-tend toute l'école asymptotique fondée par Goldwasser et Micali au début des années 1980. Un schéma est sûr si l'avantage de tout adversaire efficace est négligeable en le paramètre de sécurité, et c'est ainsi que sont définies la sécurité sémantique comme l'IND-CPA.
Le défaut, c'est que « finalement » ne dit jamais à partir de quand. Un schéma peut être prouvé sûr et pourtant cassé à 128 bits. C'est pourquoi les preuves pratiques pour les modes opératoires recourent aujourd'hui à la sécurité concrète, qui exprime l'avantage par une formule explicite en fonction du nombre de requêtes et de la taille de bloc.