Ofuscación de indistinguibilidad

Tipo de ofuscación de software criptográfico

En criptografía , la ofuscación de indistinguibilidad (abreviada como IO o iO ) es un tipo de ofuscación de software con la propiedad definitoria de que ofuscar dos programas cualesquiera que calculen la misma función matemática da como resultado programas que no se pueden distinguir entre sí. De manera informal, dicha ofuscación oculta la implementación de un programa mientras que aún permite que los usuarios lo ejecuten. ^[1] Formalmente, iO satisface la propiedad de que las ofuscaciones de dos circuitos del mismo tamaño que implementan la misma función son computacionalmente indistinguibles . ^[2]

La ofuscación de indistinguibilidad tiene varias propiedades teóricas interesantes. En primer lugar, iO es la ofuscación "mejor posible" (en el sentido de que cualquier secreto sobre un programa que pueda ser ocultado por cualquier ofuscador también puede ser ocultado por iO). En segundo lugar, iO puede usarse para construir casi toda la gama de primitivas criptográficas , incluidas las mundanas como la criptografía de clave pública y las más exóticas como el cifrado denegable y el cifrado funcional (que son tipos de criptografía que nadie sabía cómo construir antes ^{[3] ), pero con la notable excepción de las familias} de funciones hash resistentes a colisiones . Por esta razón, se la ha denominado "criptocompleta". Por último, a diferencia de muchos otros tipos de criptografía, la ofuscación de indistinguibilidad continúa existiendo incluso si P = NP (aunque tendría que construirse de manera diferente en este caso), aunque esto no implica necesariamente que iO exista incondicionalmente.

Aunque la idea de la ofuscación de software criptográfico existe desde 1996, la ofuscación de indistinguibilidad fue propuesta por primera vez por Barak et al. (2001), quienes demostraron que iO existe si P=NP es el caso. Para el caso P≠NP (que es más difícil, pero también más plausible ^[2] ), el progreso fue más lento: Garg et al. (2013) ^[4] propusieron una construcción de iO basada en un supuesto de dureza computacional relacionado con mapas multilineales , pero este supuesto fue refutado posteriormente. Una construcción basada en "supuestos bien fundados" (supuestos de dureza que han sido bien estudiados por los criptógrafos y, por lo tanto, ampliamente asumidos como seguros) tuvo que esperar hasta Jain, Lin y Sahai (2020). (Aun así, uno de estos supuestos utilizados en la propuesta de 2020 no es seguro contra las computadoras cuánticas ).

Los candidatos a ofuscación de indistinguibilidad conocidos actualmente están muy lejos de ser prácticos. Como se mide en un artículo de 2017, ^{[ necesita actualización ]} incluso ofuscar la función toy que genera la conjunción lógica de sus treinta y dos entradas de tipo de datos booleanos produce un programa de casi una docena de gigabytes de tamaño.

Definición formal

Sea un algoritmo probabilístico uniforme de tiempo polinomial . Entonces se denomina ofuscador de indistinguibilidad si y solo si satisface las dos afirmaciones siguientes: ^{[5] [6] [7]} ${\displaystyle {\mathcal {iO}}}$ ${\displaystyle {\mathcal {iO}}}$

• Completitud o funcionalidad : Para cualquier circuito booleano C de longitud de entrada n y entrada , tenemos ${\displaystyle x\in \{0,1\}^{n}}$ $${\displaystyle \Pr[C'(x)=C(x):C'\leftarrow {\mathcal {iO}}(C)]=1.}$$
• Indistinguibilidad : para cada par de circuitos del mismo tamaño k que implementan la misma funcionalidad, las distribuciones y son computacionalmente indistinguibles. En otras palabras, para cualquier adversario probabilístico en tiempo polinomial A , existe una función despreciable ( es decir , una función que eventualmente crece más lentamente que para cualquier polinomio p ) tal que, para cada par de circuitos del mismo tamaño k que implementan la misma funcionalidad, tenemos ${\displaystyle C_{0},C_{1}}$ ${\displaystyle \{{\mathcal {iO}}(C_{0})\}}$ ${\displaystyle \{{\mathcal {iO}}(C_{1})\}}$ ${\displaystyle \varepsilon (k)}$ ${\displaystyle 1/p(k)}$ ${\displaystyle C_{0},C_{1}}$ $${\displaystyle |\Pr[A({\mathcal {iO}}(C_{0}))=1]-\Pr[A({\mathcal {iO}}(C_{1}))=1]|\leq \varepsilon (k).}$$

Historia

En 2001, Barak et al., al demostrar que la ofuscación de caja negra es imposible, también propusieron la idea de un ofuscador de indistinguibilidad y construyeron uno ineficiente. ^{[8] [7] [2]} Aunque esta noción parecía relativamente débil, Goldwasser y Rothblum (2007) demostraron que un ofuscador de indistinguibilidad eficiente sería el mejor ofuscador posible, y cualquier mejor ofuscador posible sería un ofuscador de indistinguibilidad. ^{[8] [9]} (Sin embargo, para los ofuscadores ineficientes , no existe ningún mejor ofuscador posible a menos que la jerarquía polinomial colapse al segundo nivel. ^[9] )

En 2015 se creó una implementación de software de código abierto de un candidato iO. ^[10]

Construcciones de candidatos

Barak et al. (2001) demostraron que existe un ofuscador de indistinguibilidad ineficiente para los circuitos; es decir, el primer circuito lexicográficamente que calcula la misma función. ^[7] Si P = NP se cumple, entonces existe un ofuscador de indistinguibilidad, aunque no exista ningún otro tipo de criptografía. ^[2]

Garg et al. (2013) publicaron una construcción candidata de iO con seguridad demostrable bajo supuestos de dureza concretos relacionados con mapas multilineales , ^{[2] [11] [3]} pero esta suposición fue invalidada posteriormente. ^{[11] [3]} (Anteriormente, Garg, Gentry y Halevi (2012) habían construido una versión candidata de un mapa multilineal basado en supuestos heurísticos. ^[4] )

A partir de 2016, Lin comenzó a explorar construcciones de iO basadas en versiones menos estrictas de mapas multilineales, construyendo un candidato basado en mapas de grado hasta 30, y eventualmente un candidato basado en mapas de grado hasta 3. ^[3] Finalmente, en 2020, Jain, Lin y Sahai propusieron una construcción de iO basada en los supuestos de Diffie-Helman externo simétrico , aprendizaje con errores y aprendizaje más ruido , ^{[3] [5]} así como la existencia de un generador pseudoaleatorio de estiramiento superlineal en la clase de función NC ^{0. [5]} (La existencia de generadores pseudoaleatorios en NC ⁰ (incluso con estiramiento sublineal) fue un problema abierto de larga data hasta 2006. [ ^12] ) Es posible que esta construcción pueda romperse con la computación cuántica , pero existe una construcción alternativa que puede ser segura incluso contra eso (aunque esta última se basa en supuestos de seguridad menos establecidos). ^{[3] [ ¿especulación? ]}

Sentido práctico

Se han hecho intentos de implementar y evaluar candidatos iO. ^[2] En 2017, una ofuscación de la función a un nivel de seguridad de 80 bits tardó 23,5 minutos en producirse y midió 11,6 GB, con un tiempo de evaluación de 77 ms. ^[2] Además, una ofuscación del circuito de cifrado del Estándar de cifrado avanzado a un nivel de seguridad de 128 bits mediría 18 PB y tendría un tiempo de evaluación de aproximadamente 272 años. ^[2] ${\displaystyle x_{1}\wedge x_{2}\wedge \dots \wedge x_{32}}$

Existencia

Es útil dividir la cuestión de la existencia de iO utilizando los "cinco mundos" de Russell Impagliazzo , ^[13] que son cinco situaciones hipotéticas diferentes sobre la complejidad del caso promedio : ^[6]

• Algorítmica : En este caso P = NP , pero existe iO.
• Heurística : En este caso, los problemas NP son fáciles en promedio; iO no existe. ^{[ dudoso – discutir ]}
• Pessiland : En este caso, BPP ≠ NP, pero no existen funciones unidireccionales ; como resultado, iO no existe.
• Minicrypt : en este caso, existen funciones unidireccionales , pero no criptografía de clave pública segura ; iO no existe (porque se conocen construcciones explícitas de criptografía de clave pública a partir de iO y funciones unidireccionales).
• Criptomanía : En este caso existe criptografía de clave pública segura , pero iO no existe.
• Obfustopia : ^{[14] [15]} En este caso, se cree que existe iO.

Aplicaciones potenciales

Los ofuscadores de indistinguibilidad, si existen, podrían utilizarse para una enorme variedad de aplicaciones criptográficas , hasta el punto de que se los ha denominado "centro neurálgico" de la criptografía, ^{[1] [3]} la "joya de la corona de la criptografía", ^[3] o "criptocompleto". ^[2] En concreto, un ofuscador de indistinguibilidad (con el supuesto adicional de la existencia de funciones unidireccionales ^[2] ) podría utilizarse para construir los siguientes tipos de criptografía:

• Ofuscación de indistinguibilidad para programas en el modelo RAM ^[5] y para máquinas de Turing ^{[16] [17]}
• IND-CCA - criptografía de clave pública segura ^[18]
• Firmas digitales breves ^[18]
• IND-CCA : esquemas de encapsulación de claves seguras ^[18]
• Pruebas de conocimiento cero no interactivas y argumentos no interactivos concisos y de conocimiento cero perfectos ^[18]
• Protocolos de conocimiento cero concurrentes de ronda constante ^[5]
• Mapas multilineales con grados polinomiales acotados ^[5]
• Funciones de trampilla inyectivas ^[18]
• Cifrado totalmente homomórfico ^[5]
• Cifrado de testigos ^{[5] [2]}
• Cifrado funcional ^[2]
• Intercambio de secretos para cualquier lenguaje NP monótono ^[5]
• Transferencia semihonesta e inconsciente ^[18]
• Cifrado denegable (tanto denegable por el remitente como denegable por completo) ^{[18] [5] [2]}
• Intercambio de claves multipartito y no interactivo ^[5]
• RAM confusa, sucinta y segura de manera adaptativa ^[5]
• Funciones de correlación intratables ^[5]
• Cifrado basado en atributos ^[5]
• Transferencia inconsciente ^[2]
• Rastreo de traidores ^[2]
• Esquemas de codificación gradual ^[2]

Además, si existen funciones iO y unidireccionales, entonces los problemas en la clase de complejidad PPAD son demostrablemente difíciles. ^{[5] [19]}

Sin embargo, la ofuscación de indistinguibilidad no se puede utilizar para construir cada protocolo criptográfico posible: por ejemplo, ninguna construcción de caja negra puede convertir un ofuscador de indistinguibilidad en una familia de funciones hash resistente a colisiones , incluso con una permutación de puerta trampa , excepto con una pérdida exponencial de seguridad. ^[20]

Véase también

• Ofuscación de caja negra , una forma más fuerte de ofuscación que se ha demostrado que es imposible
• Principio de Kerckhoffs  : principio criptográfico que establece que todo, excepto la clave, puede ser de conocimiento público.

Referencias

1. Klarreich, Erica (3 de febrero de 2014). "Un avance en criptografía podría hacer que el software sea inhackeable". Revista Quanta . Archivado desde el original el 14 de abril de 2022. Consultado el 15 de febrero de 2019 .
2. Pellet--Mary, Alice (26 de mayo de 2020). «Co6GC: Ofuscación de programas | COSIC». www.esat.kuleuven.be . Archivado desde el original el 11 de noviembre de 2020 . Consultado el 22 de agosto de 2021 .
3. Klarreich, Erica (10 de octubre de 2020). «Los científicos informáticos consiguen la 'joya de la corona' de la criptografía». Revista Quanta . Archivado desde el original el 7 de mayo de 2022. Consultado el 10 de noviembre de 2020 .
4. Barak, Boaz (29 de diciembre de 2020). "Nuevos desarrollos en la ofuscación de indistinguibilidad (iO) | Instituto Simons para la teoría de la computación". simons.berkeley.edu . Archivado desde el original el 22 de agosto de 2021 . Consultado el 22 de agosto de 2021 .
5. Jain, Aayush; Lin, Huijia ; Sahai, Amit (2020). "Ofuscación de indistinguibilidad a partir de suposiciones bien fundadas". Archivo de criptografía ePrint . arXiv : 2008.09317 . Archivado desde el original el 2022-03-03 . Consultado el 2020-11-16 .
6. Moran, Tal; Rosen, Alon (7 de octubre de 2013). "No hay ofuscación de indistinguibilidad en Pessiland" (PDF) . Archivo de publicaciones electrónicas de criptología de la IACR . Archivado (PDF) del original el 19 de enero de 2022. Consultado el 15 de enero de 2022 .
7. Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke (3 de mayo de 2012). "Sobre la (im)posibilidad de ofuscar programas" (PDF) . Revista de la ACM . 59 (2): 6:1–6:48. doi :10.1145/2160158.2160159. ISSN  0004-5411. S2CID  2409597. Archivado (PDF) desde el original el 25 de febrero de 2023 . Consultado el 30 de junio de 2024 .
8. Klarreich, Erica (30 de enero de 2014). "Perfeccionando el arte del sinsentido sensato". Revista Quanta . Archivado desde el original el 6 de agosto de 2021. Consultado el 22 de agosto de 2021 .
9. Goldwasser, Shafi ; Rothblum, Guy N. (2007). "Sobre la mejor ofuscación posible". En Vadhan, Salil P. (ed.). Teoría de la criptografía . Apuntes de clase en informática. Vol. 4392. Berlín, Heidelberg: Springer. págs. 194–213. doi :10.1007/978-3-540-70936-7_11. hdl : 1721.1/129413 . ISBN 978-3-540-70936-7Archivado desde el original el 19 de enero de 2022. Consultado el 22 de agosto de 2021 .
10. Banescu, Sebastian; Ochoa, Martín; Kunze, Nils; Pretschner, Alexander (2015). "Idea: evaluación comparativa de la ofuscación de indistinguibilidad: una implementación candidata" (PDF) . En Piessens, Frank; Caballero, Juan; Bielova, Nataliia (eds.). Ingeniería de software y sistemas seguros . Apuntes de clase en informática. Vol. 8978. Cham: Springer International Publishing. págs. 149–156. doi :10.1007/978-3-319-15618-7_12. ISBN 978-3-319-15618-7. Archivado (PDF) del original el 22 de agosto de 2021 . Consultado el 22 de agosto de 2021 .
11. Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2013). "Ofuscación de indistinguibilidad de candidatos y cifrado funcional para todos los circuitos". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . IEEE: 40–49. doi :10.1109/focs.2013.13. ISBN 978-0-7695-5135-7.
12. Applebaum, B; Ishai, Y; Kushilevitz, E (2006). "Criptografía en NC0" (PDF) . SIAM Journal on Computing . 36 (4): 845–888. doi :10.1137/S0097539705446950. Archivado desde el original (PDF) el 2021-11-30 . Consultado el 2020-11-11 .
13. Impagliazzo, Russell (19-22 de junio de 1995). "Una visión personal de la complejidad del caso promedio". Actas de Structure in Complexity Theory. Décima Conferencia Anual del IEEE . págs. 134-147. doi :10.1109/SCT.1995.514853. ISBN. 0-8186-7052-5. S2CID  2154064. Archivado desde el original el 27 de julio de 2022 . Consultado el 27 de julio de 2022 .
14. Bitansky, Nir; Nishimaki, Ryo; Passelègue, Alain; Wichs, Daniel (30 de agosto de 2017). "De la criptomanía a la ofustopía mediante el cifrado funcional con clave secreta" (PDF) . Archivo de publicaciones electrónicas de criptología de la IACR . Archivado (PDF) del original el 20 de enero de 2022 . Consultado el 15 de enero de 2022 .
15. Garg, Sanjam; Pandey, Omkant; Srinivasan, Akshayaram; Zhandry, Mark (2017). "Rompiendo la barrera subexponencial en la ofustopía". En Coron, Jean-Sébastien; Nielsen, Jesper Buus (eds.). Avances en criptología – EUROCRYPT 2017. Apuntes de clase en informática. Vol. 10212. Cham: Springer International Publishing. págs. 156–181. doi :10.1007/978-3-319-56617-7_6. ISBN 978-3-319-56617-7Archivado desde el original el 15 de enero de 2022 . Consultado el 15 de enero de 2022 .
16. Koppula, Venkata; Lewko, Allison Bishop; Waters, Brent (14 de junio de 2015). "Indistinguishability Ofuscation for Turing Machines with Unbounded Memory" (PDF) . Actas del cuadragésimo séptimo simposio anual de la ACM sobre teoría de la computación . STOC '15. Portland, Oregón, EE. UU.: Association for Computing Machinery. págs. 419–428. doi :10.1145/2746539.2746614. ISBN . 978-1-4503-3536-2. S2CID  1368494. Archivado (PDF) del original el 2021-09-11 . Consultado el 2021-09-11 .
17. Ananth, Prabhanjan; Jain, Abhishek; Sahai, Amit (2017). "Ofuscación de indistinguibilidad para máquinas de Turing: sobrecarga constante y amortización" (PDF) . En Katz, Jonathan; Shacham, Hovav (eds.). Avances en criptología – CRYPTO 2017. Apuntes de clase en informática. Vol. 10402. Cham: Springer International Publishing. págs. 252–279. doi :10.1007/978-3-319-63715-0_9. ISBN . 978-3-319-63715-0Archivado (PDF) del original el 11 de septiembre de 2021. Consultado el 11 de septiembre de 2021 .
18. Sahai, Amit; Waters, Brent (2013). "Cómo utilizar la ofuscación de indistinguibilidad: cifrado denegable y más". Archivo de criptografía ePrint . Archivado desde el original el 2022-02-03 . Consultado el 2021-03-14 .
19. Bitansky, Nir; Paneth, Omer; Rosen, Alon (octubre de 2015). "Sobre la dificultad criptográfica de encontrar un equilibrio de Nash". 2015 IEEE 56th Annual Symposium on Foundations of Computer Science . págs. 1480–1498. doi :10.1109/FOCS.2015.94. ISBN 978-1-4673-8191-8. S2CID  217890992. Archivado desde el original el 10 de junio de 2024. Consultado el 30 de junio de 2024 .
20. Asharov, Gilad; Segev, Gil (2015). "Límites del poder de la ofuscación de indistinguibilidad y el cifrado funcional". Archivo de ePrints de criptología . Archivado desde el original el 2022-01-21 . Consultado el 2021-03-14 .