Protocolos de conocimiento cero a la medida

Un protocolo de conocimiento cero, intuitivamente, permite a un agente "demostrador" convencer a  otro agente "verificador", que un cierto hecho matemático es cierto,  sin darle conocimiento más allá de que ese hecho es cierto. Por ejemplo, permite convencer que una gráfica dada contiene un ciclo hamiltoniano, pero sin revelar las aristas de ese ciclo. O permite convencer que dada una fórmula booleana, existe una asignación de valores de verdad a sus variables que hace que la fórmula se evalúe a verdadero, pero sin revelar cuáles son los valores de las variables.

Los protocolos de conocimiento cero fueron introducidos en 1985, y a sus autores se les concedió por ello el premio Gödel en 1993. Después demostraron que para todo lenguaje en la importante clase de complejidad NP, existe un protocolo interactivo de conocimiento cero que permite convencer que una cadena dada está en ese lenguaje, sin revelar más información que ese hecho. Si bien la demostración es constructiva, el correspondiente protocolo obtenido tiene una forma muy artificial, expresado al nivel de máquinas de Turing, y por lo tanto es difícil de entender y de implementar directamente.

Debido al resultado anterior, en la literatura relacionada no se hace énfasis en cómo diseñar protocolos de conocimiento cero de forma original, a la medida, para problemas específicos. Esto es desafortunado, pues los protocolos a la medida pueden ser más fáciles de entender, más fáciles de implementar en el mundo real (y por lo tanto menos propensos a errores que comprometan su seguridad), y potencialmente más eficientes.

En esta plática divulgativa, daré una introducción a los protocolos de conocimiento cero y discutiremos un marco de trabajo original basado en teoría de gráficas, que permite diseñar de forma relativamente fácil protocolos de conocimiento cero a la medida, expresados y analizables en alto nivel, para muchos tipos de problemas; que en particular nos permite generar protocolos a la medida para más de la mitad de los famosos 21 problemas de Karp.

Trabajo conjunto con el M.C. Jorge Alberto Solano Gálvez.