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 :

• il permet la construction de nouvelles primitives cryptographiques, comme le chiffrement répudiable (proposé en 2006 comme un problème ouvert), le chiffrement fonctionnel (proposé en 2005 comme un problème ouvert), des protocoles d'échange de clé multipartite, ou de signatures propositionnelles (proposé en 2010 comme un problème ouvert) ;
• il fournit des preuves de sécurité plus simples et plus légères, certaines s'appuyant seulement sur les fonctions à sens unique (se passant notamment d'oracles aléatoires), de plus il éclaire les autres modèles de sécurité et leurs relations mutuelles ;
• il promet des compilateurs capables de protéger l'implémentation d'un algorithme contre la modification ou l'ingénierie inverse.

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 ${\mathcal {C}}_{\lambda }$de circuits (généralement les classes NC¹ ou P/poly), et on dit qu'une machine de Turing probabiliste $IO$ est un obfuscateur indistinguable pour ${\mathcal {C}}_{\lambda }$ lorsque les deux propriétés suivantes sont satisfaites :

• Pour tout paramètre de sécurité $\lambda \in \mathbb {N}$, tout circuit $C\in {\mathcal {C}}_{\lambda }$ de la forme $C:\{0,1\}^{n}\to \{0,1\}^{n}$où $n$ dépend de $\lambda$, et toute entrée $x\in \{0,1\}^{n}$, la fonctionnalité du circuit est préservée par obfuscation, c'est-à-dire :
  $$\Pr \left[C(x)=C'(x)\mid C'\gets IO(\lambda ,C)\right]=1$$
• Pour tout algorithme $D$(modélisé comme une machine de Turing probabiliste également) il existe une fonction négligeable $\alpha$ telle que ce qui suit est vrai : pour tout paramètre de sécurité $\lambda \in \mathbb {N}$, toute paire de circuits $C_{1},C_{2}\in {\mathcal {C}}_{\lambda }$ tels que $C_{1}(x)=C_{2}(x)$ pour toute entrée $x$, l'algorithme $D$ ne peut distinguer une obfuscation de $C_{1}$d'une obfuscation de $C_{2}$; mathématiquement :
  $$\left|\Pr \left[D\left(IO(\lambda ,C_{1})\right)=1\right]-\Pr \left[D\left(IO(\lambda ,C_{2})\right)=1\right]\right|\leq \alpha (\lambda )\in \operatorname {negl} (\lambda )$$
• Pour tout circuit $C\in {\mathcal {C}}_{\lambda }$, la taille du circuit après obfuscation $C'\gets IO(\lambda ,C)$ est bornée par un polynôme en $\lambda$et en $|C|$.

Notes et références