Obfuscation indistinguable

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^[1],[2],[3] 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^{[Note 2]}. Le modèle de l'obfuscation indistinguable est conçu pour échapper à ce résultat d'impossibilité tout en restant assez fort^[4] :

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

Pour toutes ces raisons, l'obfuscation indistinguable est devenue un des concepts théoriques centraux en cryptologie^[5],[15]. 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^[16], dont la sécurité est encore mal comprise^[17]. On sait aujourd'hui qu'une application trilinéaire suffit^[18], et il existe même un candidat d'obfuscation indistinguable construit à partir d'accouplements et d'apprentissage avec erreurs^[19].

On considère une classe ${\displaystyle {\mathcal {C}}_{\lambda }}$de circuits (généralement les classes NC¹ ou P/poly), et on dit qu'une machine de Turing probabiliste ${\displaystyle IO}$ est un obfuscateur indistinguable pour ${\displaystyle {\mathcal {C}}_{\lambda }}$ lorsque les deux propriétés suivantes sont satisfaites^[19] :

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