Pruebas de conocimiento cero: es como magia, pero lo explicaré

Supongamos que Peggy necesita demostrarle a Víctor que posee un secreto sin revelarlo. ¿Podrá hacerlo de manera que convenza a Víctor de que ella realmente conoce el secreto? Ésta es la pregunta central de uno de los procesos criptográficos más poderosos que podemos emplear en los sistemas de identidad: las pruebas de conocimiento cero (ZKP) .

Supongamos, por ejemplo, que Peggy tiene una licencia de conducir digital y quiere demostrarle a Víctor, el camarero, que tiene más de 21 años sin simplemente entregarle su licencia de conducir o incluso mostrarle su fecha de nacimiento. Los ZKP le permiten a Peggy demostrar que su licencia de conducir dice que tiene al menos 21 años de una manera que convence a Víctor sin que Peggy tenga que revelar nada más (es decir, no hay exceso de conocimiento).

Este problema fue explorado por primera vez por los investigadores del MIT Shafi Goldwasser, Silvio Micali y Charles Rackoff en la década de 1980 como una forma de combatir la fuga de información. El objetivo es reducir la cantidad de información adicional que el verificador, Víctor, puede aprender sobre la probadora, Peggy.

Una forma de entender cómo funcionan las ZKP es la historia de la Cueva de Alibaba, publicada por primera vez por los criptógrafos Quisquater, Guillou y Berson1. El siguiente diagrama proporciona una ilustración.

La Cueva de Alibaba tiene dos pasajes, etiquetados A y B, que se dividen en un único pasaje conectado a la entrada. Peggy posee un código secreto que le permite abrir una puerta que conecta A y B. Victor quiere comprar el código pero no pagará hasta estar seguro de que Peggy lo sabe. Peggy no lo compartirá con Víctor hasta que él pague.

El algoritmo para que Peggy demuestre que conoce el código es el siguiente:

• Víctor se queda fuera de la cueva mientras Peggy entra y selecciona uno de los pasajes. A Víctor no se le permite ver qué camino toma Peggy.
• Víctor entra a la cueva y grita "A" o "B" al azar.
• Peggy emerge del pasillo correcto porque puede desbloquear la puerta fácilmente independientemente de la elección que haya hecho al entrar.
• Por supuesto, Peggy podría haber tenido suerte y haber acertado, por lo que Peggy y Víctor repiten el experimento muchas veces.

Si Peggy siempre puede regresar por cualquier pasadizo que Víctor seleccione, entonces hay una probabilidad cada vez mayor de que Peggy realmente conozca el código. Después de 20 intentos, hay menos de una posibilidad entre un millón de que Peggy simplemente adivine qué letra llamará Víctor. Esto constituye una prueba probabilística de que Peggy conoce el secreto.

Este algoritmo no solo le permite a Peggy convencer a Víctor de que conoce el código, sino que lo hace de una manera que garantiza que Víctor no pueda convencer a nadie más de que Peggy conozca el código. Supongamos que Víctor registra toda la transacción. Lo único que ve un observador es a Víctor gritando letras y a Peggy saliendo del túnel derecho. El observador no puede estar seguro de que Víctor y Peggy no hayan acordado de antemano una secuencia de cartas para engañar a los observadores.

Por lo tanto, si bien Peggy no puede negarle a Víctor que conoce el secreto, puede negarlo a otros terceros. Esto asegura que todo lo que ella le demuestre a Víctor permanezca entre ellos y Víctor no pueda filtrarlo, al menos de una manera criptográfica que demuestre que proviene de Peggy. Peggy conserva el control tanto de su secreto como del hecho de que lo sabe.

Cuando decimos "conocimiento cero" y hablamos de que Víctor no aprende nada más allá de la proposición en cuestión, eso no es del todo cierto. En la cueva de Alibaba, Peggy demuestra, sin saberlo, que conoce el secreto. Pero hay muchas otras cosas que Víctor aprende sobre Peggy y sobre las que los ZKP no pueden hacer nada. Por ejemplo, Víctor sabe que Peggy puede oírlo, habla su idioma, camina y coopera. También podría aprender cosas sobre la cueva, como aproximadamente cuánto tiempo lleva abrir la puerta. Peggy descubre cosas similares sobre Víctor. Entonces, la realidad es que la prueba es un conocimiento aproximadamente nulo, no un conocimiento perfectamente nulo.

Sistemas ZKP

El ejemplo de la cueva de Alibaba es un uso muy específico de ZKP, lo que se llama una prueba de conocimiento de conocimiento cero . Peggy está demostrando que sabe (o posee algo). En términos más generales, es posible que Peggy quiera demostrarle muchos hechos a Víctor. Estos podrían incluir frases proposicionales o incluso valores. Los ZKP también pueden hacer eso.

Para comprender cómo podemos probar proposiciones con conocimiento cero, consideremos un ejemplo diferente, a veces llamado el Problema del Millonario Socialista . Supongamos que Peggy y Víctor quieren saber si les pagan un salario justo. Específicamente, quieren saber si se les paga la misma cantidad, pero no quieren revelar su tarifa por hora específica entre sí ni siquiera a un tercero de confianza. En este caso, Peggy no está demostrando que conoce un secreto, sino más bien una proposición de igualdad (o desigualdad).

Para simplificar, supongamos que a Peggy y Víctor se les paga $10, $20, $30 o $40 por hora.

El algoritmo funciona así:

• Peggy compra cuatro cajas con cerradura y las etiqueta como $10, $20, $30 y $40.
• Tira las llaves de todas las cajas excepto la que tiene la etiqueta de su salario.
• Peggy le da todas las cajas cerradas a Víctor, quien en privado coloca un trozo de papel con un "+" en la ranura en la parte superior de la caja etiquetada con su salario. Pone una nota con un "-" en todas las demás casillas.
• Victor le devuelve las cajas a Peggy, quien usa su llave en privado para abrir la caja con su salario.
• Si encuentra un "+", entonces ganan la misma cantidad. De lo contrario, ganan una cantidad diferente. Puede usar esto para demostrarle el hecho a Víctor.

Esto se llama transferencia ajena y demuestra que la proposición VictorSalary = PeggySalary es verdadera o falsa con conocimiento cero (es decir, sin revelar ninguna otra información).

Para que esto funcione, Peggy y Víctor deben confiar en que el otro será comunicativo y declarará su salario real. Víctor necesita confiar en que Peggy tirará las otras tres llaves. Peggy debe confiar en que Víctor pondrá sólo una hoja con un "+" en las cajas.

Así como los certificados digitales necesitan una PKI para generar confianza más allá de lo que sería posible solo con certificados autoemitidos, los ZKP son más poderosos en un sistema que permite a Peggy y Victor probar hechos a partir de lo que otros dicen sobre ellos, no solo lo que dicen sobre ellos. ellos mismos. Por ejemplo, en lugar de que Peggy y Víctor hagan su afirmación por sí mismos, supongamos que podrían confiar en un documento firmado por el departamento de recursos humanos para hacer su afirmación, de modo que ambos sepan que el otro está declarando su verdadero salario. Las credenciales verificables proporcionan un sistema para utilizar ZKP para probar muchos hechos diferentes solos o en conjunto, de manera que brinden confianza en el método y en los datos.

ZKP no interactivos

En los ejemplos anteriores, Peggy pudo demostrarle cosas a Víctor a través de una serie de interacciones. Para que las ZKP sean prácticas, las interacciones entre el probador y el verificador deben ser mínimas. Afortunadamente, una técnica llamada SNARK permite pruebas de conocimiento cero no interactivas.

Los SNARK tienen las siguientes propiedades (de donde derivan su nombre):

• Conciso: los tamaños de los mensajes son pequeños en comparación con la longitud de la prueba real.
• No interactivo : aparte de alguna configuración, el probador envía solo un mensaje al verificador.
• ARgumentos: este es realmente un argumento de que algo es correcto, no una prueba tal como lo entendemos matemáticamente. Específicamente, el demostrador teóricamente podría probar afirmaciones falsas si tuviera suficiente poder computacional. Por lo tanto, los SNARK son "computacionalmente sólidos" en lugar de "perfectamente sólidos".
• del Conocimiento: el demostrador conoce el hecho en cuestión.

Por lo general, verá "zk" (que significa conocimiento cero) pegado en el frente para indicar que durante este proceso, el verificador no aprende nada más que los hechos que se están demostrando.

Las matemáticas subyacentes a zkSNARK implican cálculo homomórfico sobre polinomios de alto grado. Pero podemos entender cómo funcionan los zkSNARK sin conocer las matemáticas subyacentes que garantizan su solidez. Si desea obtener más detalles sobre las matemáticas, le recomiendo "zkSNARKs in a Nutshell" de Christian Reitwiessner .

Como ejemplo simple, supongamos que a Víctor se le da un hash sha256 , H , de algún valor. Peggy quiere demostrar que conoce un valor s tal que sha265(s) == H sin revelarle s a Víctor. Podemos definir una función C que capture la relación:

 C(x, w) = ( sha256(w) == x )

Entonces, C(H, s) == true , mientras que otros valores para w devolverán false .

Calcular un zkSNARK requiere tres funciones G , P y V . G es el generador de claves que toma un parámetro secreto llamado lambda y la función C y genera dos claves públicas, la clave de prueba pk y la clave de verificación vk . Solo es necesario generarlos una vez para una función C determinada. El parámetro lambda debe destruirse después de este paso ya que no es necesario nuevamente y cualquiera que lo tenga puede generar pruebas falsas .

La función de prueba P toma como entrada la clave de prueba pk , una entrada pública x y un testigo privado (secreto) w . El resultado de ejecutar P(pk,x,w) es una prueba, prf , de que el probador conoce un valor de w que satisface C

La función verificadora V calcula V(vk, x, prf) , que es verdadera si la prueba prf es correcta y falsa en caso contrario.

Volviendo con Peggy y Víctor, Víctor elige una función C que representa lo que quiere que Peggy demuestre, crea un número aleatorio lambda y ejecuta G para generar las claves de prueba y verificación:

 (pk, vk) = G(C, lambda)

Peggy no debe aprender el valor de lambda . Victor comparte C , pk y vk con Peggy.

Peggy quiere demostrar que conoce el valor s que satisface C para x = H Ejecuta la función de prueba P utilizando estos valores como entradas:

 prf = P(pk, H, s)

Peggy le presenta la prf a Víctor, quien ejecuta la función de verificación:

 V(vk, H, prf)

Si el resultado es verdadero, entonces el vencedor puede estar seguro de que Peggy conoce el valor s .

No es necesario limitar la función C a un hash como lo hicimos en este ejemplo. Dentro de los límites de las matemáticas subyacentes, C puede ser bastante complicado e involucrar cualquier número de valores que a Víctor le gustaría que Peggy demostrara, todos al mismo tiempo.

Este artículo es un extracto de mi libro Learning Digital Identity , publicado por O'Reilly Media.

Notas

1. Quisquater, Jean-Jacques; Guillou, Luis C.; Berson, Thomas A. (1990). Cómo explicar los protocolos de conocimiento cero a sus hijos (PDF). Avances en criptología - CRYPTO '89: Actas. Apuntes de conferencias sobre informática. 435, págs. 628–631. doi:10.1007/0-387-34805-0_60. ISBN 978-0-387-97317-3.