Imagina que tienes algún conocimiento útil, tal vez una receta secreta o la clave de un cifrado. ¿Podrías demostrarle a un amigo que tenías ese conocimiento, sin revelar nada al respecto? Los informáticos demostraron hace más de 30 años que se podía, si se utilizaba lo que se denomina prueba de conocimiento cero.
Para entender esta idea de una forma sencilla, supongamos que quiere mostrarle a su amigo que sabe cómo atravesar un laberinto, sin revelar ningún detalle sobre el camino. Simplemente podría atravesar el laberinto dentro de un límite de tiempo, mientras que su amigo tenía prohibido mirar. (El límite de tiempo es necesario porque, dado el tiempo suficiente, cualquiera puede encontrar la salida a través de prueba y error). Tu amigo sabrá que puedes hacerlo, pero no sabrá cómo.
Las pruebas de conocimiento cero son útiles para los criptógrafos, que trabajan con información secreta, pero también para los investigadores de complejidad computacional, que se ocupan de clasificar la dificultad de diferentes problemas. “Mucha de la criptografía moderna se basa en suposiciones de complejidad, en la suposición de que ciertos problemas son difíciles de resolver, por lo que siempre ha habido algunas conexiones entre los dos mundos”, dijo. Claude Crepeau, científico informático de la Universidad McGill. “Pero [estas] pruebas han creado todo un mundo de conexión”.
Las pruebas de conocimiento cero pertenecen a una categoría conocida como pruebas interactivas, por lo que para aprender cómo funcionan las primeras, es útil comprender las segundas. Primero descrito en un artículo de 1985 de los informáticos Shafi Goldwasser, Silvio Micali y Charles Rackoff, las pruebas interactivas funcionan como un interrogatorio: a través de una serie de mensajes, una parte (el probador) intenta convencer a la otra (el verificador) de que una declaración dada es verdadera. Una prueba interactiva debe satisfacer dos propiedades. En primer lugar, una afirmación verdadera siempre acabará por convencer a un verificador honesto. En segundo lugar, si la declaración dada es falsa, ningún probador, incluso uno que pretenda poseer cierto conocimiento, puede convencer al verificador, excepto con una probabilidad insignificantemente pequeña.
Las pruebas interactivas son de naturaleza probabilística. El probador podría responder una o dos preguntas correctamente simplemente por suerte, por lo que se necesita una gran cantidad de desafíos, todos los cuales el probador debe responder correctamente, para que el verificador se sienta seguro de que el probador sabe que la declaración es verdadera.
Esta idea de las interacciones surgió cuando Micali y Goldwasser, entonces estudiantes de posgrado de la Universidad de California, Berkeley, analizaron la logística de jugar al póquer en una red. ¿Cómo pueden todos los jugadores verificar que cuando uno de ellos obtiene una carta del mazo virtual, el resultado es aleatorio? Las pruebas interactivas podrían abrir el camino. Pero entonces, ¿cómo pueden los jugadores verificar que todo el protocolo, el conjunto completo de reglas, se siguió correctamente, sin revelar la mano de cada jugador en el camino?
Para lograr este objetivo, Micali y Goldwasser agregaron una tercera propiedad a las dos necesarias para una prueba interactiva: la prueba no debe revelar nada sobre el conocimiento en sí, solo la veracidad de la declaración. “Existe la noción de pasar por un protocolo, al final del cual crees que [los jugadores de póquer] no saben nada más de lo que se supone que deben saber”, dijo Goldwasser.
Consideremos el ejemplo clásico. Alice quiere demostrarle a Bob que cierta gráfica G — una colección única de vértices (puntos) conectados por aristas (líneas) — tiene un “ciclo hamiltoniano”. Esto significa que el gráfico tiene una ruta que visita cada punto exactamente una vez y termina en el mismo punto desde el que comenzó. Alice podría hacer esto simplemente mostrándole a Bob el camino que hace esto, pero por supuesto, entonces él también conocería el camino.
Así es como Alice puede convencer a Bob de que sabe que existe ese camino, sin mostrárselo. Primero dibuja un nuevo gráfico, H, eso no parece G pero es similar de una manera crucial: tiene el mismo número de vértices, conectados de la misma manera. (Si G realmente tiene un ciclo hamiltoniano, esta similitud significa H también.) Luego, después de cubrir cada borde en H con cinta adhesiva, ella bloquea H en una caja y le da la caja a Bob. Esto evita que él lo vea directamente, pero también evita que ella lo altere. Entonces Bob toma una decisión: O puede pedirle a Alice que demuestre que H realmente es similar a G, o puede pedirle que le muestre el ciclo hamiltoniano en H. Ambas solicitudes deberían ser fáciles para Alice, asumiendo que H realmente es lo suficientemente similar a G, y que ella realmente conoce el camino.
Por supuesto, incluso si Alice no conoce el ciclo hamiltoniano en G, puede tratar de engañar a Bob, ya sea dibujando gráficos que no sean similares a G, o enviando gráficos para los que no conoce la ruta. Pero después de haber jugado varias rondas, la posibilidad de que Alice engañe a Bob cada vez se vuelve cada vez más pequeña. Si lo hace todo bien, finalmente Bob se convencerá de que Alice conoce un ciclo hamiltoniano en forma gráfica. G, sin que Bob lo haya visto nunca.
Después del artículo inicial que describió por primera vez tales pruebas, Micali y dos matemáticos, Oded Goldreich y Avi Wigderson, descubrieron una consecuencia inesperada con efectos de largo alcance. Tiene que ver con una categoría principal de problemas de dificultad aproximadamente igual, conocida como NP. Estos problemas son difíciles de resolver, pero sus soluciones son fáciles de verificar. Los tres investigadores encontrado que, si es un cifrado verdaderamente seguro es posible, entonces la solución a cada problema en NP también se puede probar con una prueba de conocimiento cero. Este estudio ayudó a los investigadores concebir variantes de pruebas de conocimiento cero que ni siquiera requieren encriptación segura en primer lugar; estos se conocen como pruebas interactivas de probadores múltiples.
Y en 1988, Micali y otros mostró que si un probador y un verificador comparten una cadena corta de bits aleatorios, no es necesaria ninguna interacción. En teoría, esto significaba que las pruebas de conocimiento cero no tienen que ser interactivas, lo que implicaría que la comunicación constante entre dos partes no es necesaria. Esto los haría mucho más útiles para los investigadores, pero no fue hasta después del cambio de siglo XXI que tales pruebas despegaron.
“A fines de la década de 2000, comenzamos a ver la evolución de técnicas eficientes para construir pruebas de conocimiento cero”, dijo Mateo D. Verde, un criptógrafo de la Universidad John Hopkins. "Llegamos al punto en que nos dimos cuenta, 'Espera un segundo, en realidad podría haber una manera de usar esto en la práctica'".
Ahora, un probador podría enviar un solo mensaje a un verificador sin que ambos tengan que estar en línea, y los investigadores podrían crear una prueba muy breve que podría verificarse rápidamente, incluso para problemas muy complicados. Esto ha dado lugar a varios usos prácticos, como la capacidad de verificar rápidamente la cadena de bloques después de una transacción de criptomonedas mientras se ocultan los detalles de la transacción. Y en 2016, un grupo de físicos mostró cómo las pruebas de conocimiento cero pueden ayudar con el desarme nuclear: sin revelar ningún secreto sobre el diseño de su ojiva nuclear, un país ahora podría demostrar a los inspectores nucleares si la ojiva está activa o inactiva.
Más recientemente, los avances en la computación cuántica han obligado a Crépeau a realizar pruebas de estrés en investigaciones anteriores para asegurarse de que los protocolos de conocimiento cero sigan siendo viables. En 2021, ayudó demostrar que las pruebas interactivas de múltiples probadores mantienen su secreto incluso cuando se involucran computadoras cuánticas, pero lograr el mismo nivel de seguridad hace que el protocolo sea mucho más lento. El hallazgo fue una buena noticia, dijo, pero surgirán nuevas preocupaciones a medida que avance la tecnología.
“Cada tipo de computación que podamos hacer en el futuro involucrará computadoras cuánticas”, dijo Crépeau. “Entonces, como buenos criptógrafos paranoicos, cada vez que evaluamos la seguridad de un sistema, queremos asegurarnos de que nuestro sistema sea seguro”.
Nota del editor: Shafi Goldwasser ha recibido financiación de la Fundación Simons, que también financia este publicación editorialmente independiente. Las decisiones de financiación de la Fundación Simons no tienen influencia en nuestra cobertura.
