Amplifying Randomized Encodings & Applications

En el vasto panorama de la criptografía moderna, existe una tensión fundamental entre la seguridad y la eficiencia. Queremos sistemas que sean increíblemente difíciles de romper, pero lo suficientemente simples como para ejecutarse en dispositivos cotidianos. Para lograr esto, los criptógrafos suelen recurrir a las "funciones de un solo sentido", operaciones matemáticas que son fáciles de realizar en una dirección pero casi imposibles de revertir sin una clave secreta. La existencia de estas funciones es la base de la privacidad digital y, sin embargo, durante décadas, los matemáticos han luchado por demostrar que existen basándose en los problemas más difíciles posibles de la informática. En lugar de depender de supuestos específicos y potencialmente frágiles, los investigadores han buscado durante mucho tiempo demostrar que las funciones de un solo sentido deben existir simplemente porque ciertas clases amplias de problemas son inherentemente difíciles de resolver. Entre estas clases de problemas difíciles se encuentran los problemas que involucran "pruebas de conocimiento cero", un método mediante el cual una parte puede convencer a otra de que conoce un secreto sin revelar ningún detalle sobre el secreto mismo. La pregunta ha sido: si estos problemas de conocimiento cero son difíciles de resolver en el peor de los casos, ¿garantiza eso la existencia de las funciones de un solo sentido necesarias para el cifrado seguro?

Un equipo de investigadores ha dado ahora un paso significativo para responder a esta pregunta mediante el desarrollo de una nueva forma de amplificar la fiabilidad de las "codificaciones aleatorizadas". Imagine una codificación aleatorizada como una forma de traducir un problema complejo a una versión más simple y codificada. El objetivo es crear una traducción que no revele nada sobre el problema original más allá de la respuesta final, siendo al mismo tiempo mucho más fácil de computar que el original. Los investigadores se centraron en un tipo específico de estas traducciones donde la garantía de seguridad se mantiene solo para las respuestas "sí", un escenario conocido como codificación de un solo lado. Descubrieron que, incluso si estas codificaciones son inicialmente imperfectas —lo que significa que podrían filtrar una pequeña cantidad de información o dar la respuesta incorrecta ocasionalmente—, pueden mejorarse sistemáticamente. Al aplicar una nueva técnica basada en el concepto de "reducciones de pérdida", que mide cuánta información se descarta durante una transformación, el equipo demostandó que estas codificaciones defectuosas pueden amplificarse hasta que los errores y las fugas de información se vuelvan ínfimos, volviéndose efectivamente despreciables.

Este proceso de amplificación es la clave para desbloquear conexiones más profundas en la informática. Los investigadores demostraron que si un problema puede codificarse con un nivel modesto de privacidad y corrección, puede transformarse en una versión prácticamente perfecta. Aplicaron este hallazgo a la clase de problemas conocida como NISZK, que trata con pruebas de conocimiento cero no interactivas. Durante años, fue una cuestión abierta si la propiedad de conocimiento cero de estas pruebas podía fortalecerse de una garantía de inverso-polinómica débil a una fuerte y despreciable. El equipo demostró que puede hacerlo, resolviendo un problema que había permanecido sin respuesta desde finales de la década de 1990. Esto significa que cualquier problema con una prueba de conocimiento cero débil puede convertirse en uno con una garantía de conocimiento cero prácticamente perfecta, siempre que el problema subyacente sea lo suficientemente difícil.

Las implicaciones de este trabajo se extienden directamente a la existencia de las funciones de un solo sentido. Los investigadores demostraron que si las versiones del peor caso de estos problemas de conocimiento cero son de hecho difíciles de resolver, entonces las funciones de un solo sentido deben existir, siempre que se pueda establecer un procedimiento específico de eliminación de errores para las codificaciones de un solo lado. Lograron esto demostrando que la capacidad de eliminar errores de las codificaciones de un solo lado es suficiente para cerrar la brecha entre la dificultad de estos problemas específicos y la creación de herramientas criptográficas seguras. Si bien el artículo establece que esta eliminación de errores sería suficiente, deja explícitamente la construcción de tal algoritmo de eliminación de errores como una cuestión abierta para trabajos futuros. Además, exploraron el reino cuántico, mostrando que principios similares se aplcan a las codificaciones cuánticas, lo que a su vez implica la existencia de "generadores de estados de un solo sentido", un equivalente cuántico de las funciones de un solo sentido. Esto sugiere que la dificultad fundamental de estos problemas es lo suficientemente robusta como para soportar la criptografía tanto clásica como cuántica.

El estudio también abordó la naturaleza de la "ofuscación de indistinguibilidad", una poderosa herramienta criptográfica que oculta el funcionamiento interno de un programa informático mientras preserva su función. Investigaciones previas habían demostrado que la ofuscación implica funciones de un solo sentido solo bajo condiciones muy estrictas donde el programa está perfectamente oculto o tiene un error muy bajo. El nuevo trabajo demuestra que incluso si la ofuscación es débil e imperfecta —filtrando una cantidad significativa de información y cometiendo errores frecuentes—, sigue implicando la existencia de funciones de un solo sentido, siempre y cuando una estructura teórica importante en la informática conocida como la Jerarquía Polinómica no colapse. Este hallazgo amplía significamente las condiciones bajo las cuales podemos estar seguros de que la criptografía segura es posible, sugiriendo que la barrera para construirla es más baja y robusta de lo que se pensaba anteriormente.

Al establecer estas conexiones, los investigadores han proporcionado un mapa más claro de los fundamentos teóricos de la criptografía. Demostraron que la dificultad de resolver ciertas clases amplias de problemas no es solo una curiosidad matemática abstracta, sino una fuente directa de la seguridad necesaria para nuestro mundo digital. Su trabajo confirma que si podemos confiar en que estos problemas complejos son difíciles de resolver en los peores casos, y si se resuelve la cuestión abierta de la eliminación de errores para las codificaciones de un solo lado, podemos confiar en la existencia de las funciones de un solo sentido que mantienen nuestros datos seguros. Los resultados no solo sugieren una posibilidad; ofrecen una prueba rigurosa de que el camino desde los problemas difíciles hacia el cifrado seguro está abierto, supeditado al refinamiento exitoso de las técnicas de codificación para eliminar errores. Esto acerca a la comunidad teórica a una comprensión definitiva de por qué funciona la criptografía y qué es lo que realmente se necesita para construirla.