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: . (ZKP) las pruebas de conocimiento cero 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 de conocimiento). exceso 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 que el verificador, Víctor, puede aprender sobre la probadora, Peggy. adicional 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 de que Peggy conoce el secreto. prueba probabilística 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. Tenga en cuenta que esta propiedad depende de que el algoritmo utilice un buen generador de números pseudoaleatorios con una semilla de alta entropía para que Peggy y los observadores externos no puedan predecir las elecciones de Víctor. 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 nulo, no un conocimiento nulo. aproximadamente perfectamente Sistemas ZKP El ejemplo de la cueva de Alibaba es un uso muy específico de ZKP, lo que se llama una . 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. prueba de conocimiento de conocimiento cero Para comprender cómo podemos probar proposiciones con conocimiento cero, consideremos un ejemplo diferente, a veces llamado el . 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). Problema del Millonario Socialista 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 y demuestra que la proposición es verdadera o falsa con conocimiento cero (es decir, sin revelar ninguna otra información). transferencia ajena VictorSalary = PeggySalary 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. 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. Las credenciales verificables 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. tienen las siguientes propiedades (de donde derivan su nombre): Los SNARK los tamaños de los mensajes son pequeños en comparación con la longitud de la prueba real. Conciso: : aparte de alguna configuración, el probador envía solo un mensaje al verificador. No interactivo 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". ARgumentos: el demostrador conoce el hecho en cuestión. del Conocimiento: 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 , , de algún valor. Peggy quiere demostrar que conoce un valor tal que sin revelarle a Víctor. Podemos definir una función que capture la relación: sha256 H s sha265(s) == H s C C(x, w) = ( sha256(w) == x ) Entonces, , mientras que otros valores para devolverán . C(H, s) == true w false Calcular un zkSNARK requiere tres funciones , y . es el generador de claves que toma un parámetro secreto llamado y la función y genera dos claves públicas, la clave de prueba y la clave de verificación . Solo es necesario generarlos una vez para una función determinada. El parámetro debe destruirse después de este paso ya que no es necesario nuevamente y cualquiera que lo tenga puede generar pruebas . G P V G lambda C pk vk C lambda falsas La función de prueba toma como entrada la clave de prueba , una entrada pública y un testigo privado (secreto) . El resultado de ejecutar es una prueba, , de que el probador conoce un valor de que satisface P pk x w P(pk,x,w) prf w C La función verificadora calcula , que es verdadera si la prueba es correcta y falsa en caso contrario. V V(vk, x, prf) prf Volviendo con Peggy y Víctor, Víctor elige una función que representa lo que quiere que Peggy demuestre, crea un número aleatorio y ejecuta para generar las claves de prueba y verificación: C lambda G (pk, vk) = G(C, lambda) Peggy no debe aprender el valor de . Victor comparte , y con Peggy. lambda C pk vk Peggy quiere demostrar que conoce el valor que satisface para Ejecuta la función de prueba utilizando estos valores como entradas: s C x = H P prf = P(pk, H, s) Peggy le presenta la a Víctor, quien ejecuta la función de verificación: prf 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 a un hash como lo hicimos en este ejemplo. Dentro de los límites de las matemáticas subyacentes, 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. C C Este artículo es un extracto de mi libro , publicado por O'Reilly Media. Learning Digital Identity Notas 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. También publicado aquí.
