PICSI

Cryptographie à bas coût: définition (tentative)

    La cryptographie à bas coût n'a pas encore de définition bien établie. Intuitivement, elle désigne l'ensemble des systèmes cryptographiques qui peuvent être implantés avec des ressources informatiques limitées. Mais cette caractérisation bien vague pose un certain nombre de questions. S'agit-il de ressources limitées en temps, en espace, en portes logiques, en énergie,… en euros ? Les contraintes sont-elles absolues (par exemple : le système doit pouvoir être implanté sur une carte à microprocesseur) ou relatives (par exemple : le mécanisme doit permettre de produire une signature numérique dix fois plus rapidement que RSA) ? De quelle composante du système parle-t-on : production de clé, chiffrement, déchiffrement ? Signature, authentification, vérification ? Recherche-t-on plutôt des "structures" mathématiques permettant par elles-mêmes de limiter les ressources ou bien des "objets isolés" ?

    Ces questions ne constituent pas un exercice gratuit : faute de se les poser, rares sont les systèmes qui ne pourraient pas revendiquer l'appellation "bas coût". Après tout, RSA est presque imbattable en vérification de signature et DES peut être exécuté en quelques millisecondes en logiciel sur une carte à puce standard (et même quelques microsecondes s'il est directement câblé). Or il n'existe pratiquement pas d'algorithme symétrique (resp. algorithme asymétrique) qui n'améliore d'une façon ou d'une autre les performances de DES (resp. de RSA). Il convient donc d'être plus sélectif.
Les besoins observés ainsi que la perception par la communauté de la notion de "bas coût" conduisent à donner la définition suivante, que le temps se chargera d'améliorer :

Définition (informelle): Un système cryptographique est dit "à bas coût" si le (ou l'un des) mécanisme(s) utilisant la clé secrète peut être exécuté à un coût et/ou en un temps d'exécution dont l'ordre de grandeur est au moins une fois inférieur à celui d'un mécanisme standard de la même famille.