Obfuscation indistinguable

En cryptologie, l'obfuscation indistinguable ou iO^{[Note 1]} 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^[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].

Définition

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|}$.

Notes et références

Notes

1. Pour l'anglais indistinguishability obfuscation. Il ne semble pas s'être imposé de traduction francophone de l'expression, qui pourrait également être rendue par « obfuscation d'indistinction ». Dans tous les cas l'expression « obfuscation indistinguable » semble aujourd'hui l'expression francophone majoritaire (voir par exemple Tancrède Lepoint, Design and Implementation of Lattice-Based Cryptography, Ecole Normale Supérieure de Paris - ENS Paris, 30 juin 2014 (lire en ligne).
2. Précisément, ils ont montré l'existence de fonctions impossibles à obfusquer ${\displaystyle f_{s}}$telles que pour toute implémentation de ${\displaystyle f_{s}}$il existe une procédure efficace d'extraction de ${\displaystyle s}$(le « secret » de ${\displaystyle f_{s}}$). De plus, de telles fonctions existent avec une complexité de circuit faible.

Références

1. (en) Boaz Barak, Oded Goldreich, Rusell Impagliazzo et Steven Rudich, « On the (Im)possibility of Obfuscating Programs », dans Advances in Cryptology — CRYPTO 2001, Springer Berlin Heidelberg, 2001 (ISBN 9783540424567, DOI 10.1007/3-540-44647-8_1, lire en ligne), p. 1–18
2. (en) Boaz Barak, Oded Goldreich, Russell Impagliazzo et Steven Rudich, « On the (im)possibility of obfuscating programs », Journal of the ACM (JACM), vol. 59, n^o 2,‎ 1^er avril 2012, p. 6 (ISSN 0004-5411, DOI 10.1145/2160158.2160159, lire en ligne, consulté le 19 août 2018)
3. (en) Mohammad Mahmoody, Ameer Mohammed et Soheil Nematihaji, « On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models », dans Theory of Cryptography, Springer Berlin Heidelberg, 19 décembre 2015 (ISBN 9783662490952, DOI 10.1007/978-3-662-49096-9_2, lire en ligne), p. 18–48
4. (en) Shafi Goldwasser et Guy N. Rothblum, « On Best-Possible Obfuscation », Journal of Cryptology, vol. 27, n^o 3,‎ 22 mai 2013, p. 480–505 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-013-9151-z, lire en ligne, consulté le 19 août 2018)
5. (en) Amit Sahai et Brent Waters, « How to use indistinguishability obfuscation: deniable encryption, and more », STOC '14 Proceedings of the forty-sixth annual ACM symposium on Theory of computing, ACM,‎ 31 mai 2014, p. 475–484 (ISBN 9781450327107, DOI 10.1145/2591796.2591825, lire en ligne, consulté le 19 août 2018)
6. (en) Rein Canetti, Cynthia Dwork, Moni Naor et Rafail Ostrovsky, « Deniable Encryption », dans Advances in Cryptology — CRYPTO '97, Springer Berlin Heidelberg, 1997 (ISBN 9783540633846, DOI 10.1007/bfb0052229, lire en ligne), p. 90–104
7. (en) Sanjam Garg, Craig Gentry, Shai Halevi et Mariana Raykova, « Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits », SIAM Journal on Computing, vol. 45, n^o 3,‎ janvier 2016, p. 882–929 (ISSN 0097-5397 et 1095-7111, DOI 10.1137/14095772x, lire en ligne, consulté le 19 août 2018)
8. (en) Amit Sahai et Brent Waters, « Fuzzy Identity-Based Encryption », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2005 (ISBN 9783540259107, DOI 10.1007/11426639_27, lire en ligne), p. 457–473
9. (en) Dan Boneh, Amit Sahai et Brent Waters, « Functional Encryption: Definitions and Challenges », dans Theory of Cryptography, Springer Berlin Heidelberg, 2011 (ISBN 9783642195709, DOI 10.1007/978-3-642-19571-6_16, lire en ligne), p. 253–273
10. (en) Dan Boneh et Mark Zhandry, « Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation », Algorithmica, vol. 79, n^o 4,‎ 15 novembre 2016, p. 1233–1285 (ISSN 0178-4617 et 1432-0541, DOI 10.1007/s00453-016-0242-8, lire en ligne, consulté le 19 août 2018)
11. (en) Chen Qian, Mehdi Tibouchi et Rémi Géraud, « Universal Witness Signatures », dans Advances in Information and Computer Security, Springer International Publishing, 2018 (ISBN 9783319979151, DOI 10.1007/978-3-319-97916-8_20, lire en ligne), p. 313–329
12. David Naccache, Is theoretical cryptography any good in practice? CRYPTO & CHES 2010 invited talk (2010)
13. (en) Susan Hohenberger, Amit Sahai et Brent Waters, « Replacing a Random Oracle: Full Domain Hash from Indistinguishability Obfuscation », dans Advances in Cryptology – EUROCRYPT 2014, Springer Berlin Heidelberg, 2014 (ISBN 9783642552199, DOI 10.1007/978-3-642-55220-5_12, lire en ligne), p. 201–220
14. (en) Christina Brzuska, Pooya Farshim et Arno Mittelbach, « Random-Oracle Uninstantiability from Indistinguishability Obfuscation », dans Theory of Cryptography, Springer Berlin Heidelberg, 2015 (ISBN 9783662464960, DOI 10.1007/978-3-662-46497-7_17, lire en ligne), p. 428–455
15. (en) Ran Canetti, « Indistinguishability Obfuscation and Multi-linear Maps: A Brave New World », sur blog.simons.berkeley.edu, juillet 2015 (consulté le 19 août 2018)
16. (en) Sanjam Garg, Craig Gentry et Shai Halevi, « Candidate Multilinear Maps from Ideal Lattices », dans Advances in Cryptology – EUROCRYPT 2013, Springer Berlin Heidelberg, 2013 (ISBN 9783642383472, DOI 10.1007/978-3-642-38348-9_1, lire en ligne), p. 1–17
17. (en) Eric Miles, Amit Sahai et Mark Zhandry, « Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13 », dans Advances in Cryptology – CRYPTO 2016, Springer Berlin Heidelberg, 2016 (ISBN 9783662530078, DOI 10.1007/978-3-662-53008-5_22, lire en ligne), p. 629–658
18. (en) Huijia Lin et Stefano Tessaro, « Indistinguishability Obfuscation from Trilinear Maps and Block-Wise Local PRGs », dans Advances in Cryptology – CRYPTO 2017, Springer International Publishing, 2017 (ISBN 9783319636870, DOI 10.1007/978-3-319-63688-7_21, lire en ligne), p. 630–660
19. (en) Prabhanjan Ananth, Aayush Jain, Dakshita Khurana et Amit Sahai, « Indistinguishability Obfuscation Without Multilinear Maps: iO from LWE, Bilinear Maps, and Weak Pseudorandomness », IACR ePrint Archive,‎ 2018 (lire en ligne)