Obfuscation indistinguable

En cryptologie, l'obfuscation indistinguable ou iO est un modèle de sécurité dans lequel on peut espérer prouver certaines propriétés cryptologiques. Ce modèle postule l'existence d'un algorithme efficace dont l'effet approximatif est de réécrire un programme informatique, de sorte qu'un adversaire ne parvienne pas à distinguer de manière fiable deux programmes ainsi réécrits, lorsque ces derniers sont assez similaires. L'existence postulée d'un tel algorithme, pour lequel plusieurs candidats sont aujourd'hui proposés, a des conséquences importantes en cryptologie et en sécurité informatique.

Histoire et motivation

L'obfuscation indistinguable a été introduite en 2001 par les cryptologues Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan et Ke Yang,, après que ceux-ci ont montré qu'il n'existe pas d'algorithme d'obfuscation « en boîte noire », c'est-à-dire capable de masquer le fonctionnement de tout programme à un adversaire. Le modèle de l'obfuscation indistinguable est conçu pour échapper à ce résultat d'impossibilité tout en restant assez fort :

Pour toutes ces raisons, l'obfuscation indistinguable est devenue un des concepts théoriques centraux en cryptologie,. La question s'est donc rapidement posée de construire des algorithmes compatibles avec ce modèle : il s'agit à l'heure actuelle (2018) d'un problème encore largement ouvert. Plusieurs candidats ont été proposés, initialement à partir d'applications mulilinéaires cryptographiques, dont la sécurité est encore mal comprise. On sait aujourd'hui qu'une application trilinéaire suffit, et il existe même un candidat d'obfuscation indistinguable construit à partir d'accouplements et d'apprentissage avec erreurs.

Définition

On considère une classe 𝒞λde circuits (généralement les classes NC1 ou P/poly), et on dit qu'une machine de Turing probabiliste IO est un obfuscateur indistinguable pour 𝒞λ lorsque les deux propriétés suivantes sont satisfaites :