En criptografía , una prueba de conocimiento cero o protocolo de conocimiento cero es un método mediante el cual una parte (el probador) puede demostrarle a otra parte (el verificador) que una determinada afirmación es verdadera, evitando al mismo tiempo transmitir al verificador cualquier información más allá de la el mero hecho de la verdad de esa afirmación. [1] La intuición que subyace a las pruebas de conocimiento cero es que es trivial demostrar la posesión de la información relevante simplemente revelándola; la parte difícil es probar esta posesión sin revelar esta información (o cualquier aspecto de ella). [2]
Teniendo en cuenta que sólo se debería poder demostrar una afirmación si se dispone de cierta información secreta relacionada con ella, el verificador, incluso después de haberse convencido de la veracidad de la afirmación, no debería poder probar la verdad de la afirmación. declaración a otros terceros.
En el modelo simple , las pruebas no triviales de conocimiento cero (es decir, aquellas para lenguajes fuera de BPP ) exigen interacción entre el probador y el verificador. [3] Esta interacción suele implicar la selección de uno o más desafíos aleatorios por parte del verificador; A pesar del origen aleatorio de estos desafíos, junto con las respuestas exitosas del probador, convencen conjuntamente al verificador de que el probador posee el conocimiento reclamado. (Si no hubiera interacción, entonces el verificador, habiendo obtenido la transcripción de ejecución del protocolo, es decir, el único mensaje del probador, podría reproducir esa transcripción a un tercero, convenciendo así al tercero de que el verificador también poseía la información secreta. )
En los modelos comunes de cadenas aleatorias y de oráculos aleatorios , existen pruebas de conocimiento cero no interactivas , a la luz de la heurística Fiat-Shamir . [4] [5] [6] Estas pruebas, en la práctica, se basan en suposiciones computacionales (normalmente la resistencia a colisiones de una función hash criptográfica ).
Hay una historia muy conocida que presenta las ideas fundamentales de las pruebas de conocimiento cero, publicada por primera vez en 1990 por Jean-Jacques Quisquater y otros en su artículo "Cómo explicar los protocolos de conocimiento cero a sus hijos". [7] Las dos partes en la historia de la prueba de conocimiento cero son Peggy como la demostradora de la afirmación, y Víctor , el verificador de la afirmación.
En esta historia, Peggy ha descubierto la palabra secreta utilizada para abrir una puerta mágica en una cueva. La cueva tiene forma de anillo, con la entrada en un lado y la puerta mágica bloqueando el lado opuesto. Víctor quiere saber si Peggy conoce la palabra secreta; pero Peggy, al ser una persona muy reservada, no quiere revelar su conocimiento (la palabra secreta) a Víctor ni revelar el hecho de su conocimiento al mundo en general.
Etiquetan los caminos izquierdo y derecho desde las entradas A y B. Primero, Víctor espera fuera de la cueva mientras Peggy entra. Peggy toma el camino A o B; A Víctor no se le permite ver qué camino toma. Luego, Víctor entra a la cueva y grita el nombre del camino que quiere que ella use para regresar, ya sea A o B, elegido al azar. Siempre que conozca realmente la palabra mágica, esto es fácil: abre la puerta, si es necesario, y regresa por el camino deseado.
Sin embargo, supongamos que ella no conocía la palabra. Entonces, solo podría regresar por el camino nombrado si Víctor le diera el nombre del mismo camino por el que había entrado. Como Víctor elegiría A o B al azar, tendría un 50% de posibilidades de adivinar correctamente. Si repitieran este truco muchas veces, digamos 20 veces seguidas, su probabilidad de anticipar con éxito todas las solicitudes de Víctor se reduciría a 1 en 2 20 , o 9,56 × 10 −7 .
Por lo tanto, si Peggy aparece repetidamente en la salida nombrada por Víctor, puede concluir que es extremadamente probable que Peggy, de hecho, conozca la palabra secreta.
Una nota al margen con respecto a los observadores externos: incluso si Víctor lleva una cámara oculta que graba toda la transacción, lo único que grabará la cámara es, en un caso, que Víctor grite "¡A!" y Peggy aparece en A o en el otro caso Víctor gritando "¡B!" y Peggy apareciendo en B. Una grabación de este tipo sería trivial para que dos personas la falsificaran (requiriendo sólo que Peggy y Víctor se pongan de acuerdo de antemano sobre la secuencia de A y B que Víctor gritará). Seguramente una grabación así nunca convencerá a nadie más que a los participantes originales. De hecho, incluso una persona que estuvo presente como observador en el experimento original no estaría convencida, ya que Victor y Peggy podrían haber orquestado todo el "experimento" de principio a fin.
Además, si Víctor elige sus A y B lanzando una moneda al aire frente a la cámara, este protocolo pierde su propiedad de conocimiento cero; el lanzamiento de la moneda frente a la cámara probablemente sería convincente para cualquiera que viera la grabación más tarde. Por lo tanto, aunque esto no le revela la palabra secreta a Víctor, sí le permite convencer al mundo en general de que Peggy tiene ese conocimiento, en contra de los deseos declarados de Peggy. Sin embargo, la criptografía digital generalmente "lanza monedas" basándose en un generador de números pseudoaleatorios , que es similar a una moneda con un patrón fijo de caras y cruces conocido sólo por el propietario de la moneda. Si la moneda de Víctor se comportara de esta manera, nuevamente sería posible que Víctor y Peggy hubieran falsificado el experimento, por lo que usar un generador de números pseudoaleatorios no revelaría el conocimiento de Peggy al mundo de la misma manera que lo haría el uso de una moneda lanzada al aire.
Observe que Peggy podría demostrarle a Víctor que conoce la palabra mágica, sin revelársela, en una sola prueba. Si Víctor y Peggy van juntos a la boca de la cueva, Víctor podrá ver a Peggy entrar por A y salir por B. Esto probaría con certeza que Peggy conoce la palabra mágica, sin revelarle la palabra mágica a Víctor. Sin embargo, dicha prueba podría ser observada por un tercero o grabada por Víctor y sería convincente para cualquiera. En otras palabras, Peggy no pudo refutar tal prueba afirmando que estuvo en connivencia con Víctor y, por lo tanto, ya no tiene el control de quién está al tanto de su conocimiento.
Imagina que tu amigo "Víctor" es daltónico ( mientras que tú no lo eres) y tienes dos bolas: una roja y otra verde, pero por lo demás idénticas. A Víctor las bolas le parecen completamente idénticas. Víctor se muestra escéptico de que las bolas sean realmente distinguibles. Quieres demostrarle a Víctor que las bolas en realidad tienen colores diferentes , pero nada más. En particular, no querrás revelar qué bola es la roja y cuál es la verde.
Aquí está el sistema de prueba. Le das las dos pelotas a Víctor y él se las pone a la espalda. A continuación, toma una de las bolas, la saca de detrás de su espalda y la muestra. Luego la vuelve a colocar detrás de su espalda y luego elige revelar solo una de las dos bolas, eligiendo una de las dos al azar con la misma probabilidad. Él te preguntará: "¿Cambié la pelota?" Luego todo este procedimiento se repite tantas veces como sea necesario.
Al observar los colores de las bolas, puedes, por supuesto, decir con certeza si las cambió o no. Por otro lado, si las bolas fueran del mismo color y, por tanto, indistinguibles, no hay forma de adivinar correctamente con una probabilidad superior al 50%.
Dado que la probabilidad de que hubiera logrado identificar aleatoriamente cada interruptor/no interruptor es del 50%, la probabilidad de haber tenido éxito aleatoriamente en todos los interruptores/no interruptores se aproxima a cero ("solidez"). Si usted y su amigo repiten esta "prueba" varias veces (por ejemplo, 20 veces), su amigo debería convencerse ("completitud") de que las bolas en realidad tienen colores diferentes.
La prueba anterior es de conocimiento cero porque tu amigo nunca aprende qué bola es verde y cuál es roja; de hecho, no adquiere ningún conocimiento sobre cómo distinguir las bolas. [8]
Un ejemplo bien conocido de prueba de conocimiento cero es el ejemplo de "¿Dónde está Waldo?". En este ejemplo, el probador quiere demostrarle al verificador que sabe dónde está Waldo en una página de ¿ Dónde está Waldo? libro, sin revelar su ubicación al verificador. [9]
El probador comienza tomando una gran pizarra negra con un pequeño agujero, del tamaño de Waldo. El tablero tiene el doble del tamaño del libro en ambas direcciones, por lo que el verificador no puede ver en qué parte de la página lo está colocando. Luego, el probador coloca el tablero sobre la página para que Waldo esté en el hoyo. [9]
El verificador ahora puede mirar a través del agujero y ver a Waldo, pero no puede ver ninguna otra parte de la página. Por tanto, el probador ha demostrado al verificador que sabe dónde está Waldo, sin revelar ninguna otra información sobre su ubicación. [9]
Este ejemplo no es una prueba perfecta de conocimiento cero, porque el demostrador revela cierta información sobre la ubicación de Waldo, como la posición de su cuerpo. Sin embargo, es una ilustración decente del concepto básico de prueba de conocimiento cero.
Una prueba de conocimiento cero de alguna afirmación debe satisfacer tres propiedades:
Las dos primeras son propiedades de sistemas de prueba interactivos más generales . El tercero es lo que hace que la prueba sea de conocimiento cero. [10]
Las pruebas de conocimiento cero no son pruebas en el sentido matemático del término porque existe una pequeña probabilidad, el error de solidez , de que un demostrador tramposo pueda convencer al verificador de una afirmación falsa. En otras palabras, las pruebas de conocimiento cero son "pruebas" probabilísticas más que deterministas. Sin embargo, existen técnicas para disminuir el error de solidez a valores insignificantes (por ejemplo, adivinar correctamente cien o mil decisiones binarias tiene un error de solidez o , respectivamente. A medida que aumenta el número de bits, el error de solidez disminuye hacia cero) .
Una definición formal de conocimiento cero tiene que utilizar algún modelo computacional, siendo el más común el de una máquina de Turing . Sean , , y máquinas de Turing. Un sistema de prueba interactivo para un idioma tiene conocimiento cero si para cualquier verificador de tiempo polinómico probabilístico (PPT) existe un simulador de PPT tal que:
donde hay un registro de las interacciones entre y . Se modela que el probador tiene un poder de cálculo ilimitado (en la práctica, suele ser una máquina probabilística de Turing ). Intuitivamente, la definición establece que un sistema de prueba interactivo tiene conocimiento cero si para cualquier verificador existe un simulador eficiente (dependiendo de ) que pueda reproducir la conversación entre y sobre cualquier entrada dada. La cadena auxiliar en la definición desempeña el papel de "conocimiento previo" (incluidas las monedas aleatorias de ). La definición implica que no se puede utilizar ninguna cadena de conocimiento previo para extraer información de su conversación con , porque si también se le proporciona este conocimiento previo, entonces puede reproducir la conversación entre y tal como antes. [ cita necesaria ]
La definición dada es la de conocimiento cero perfecto. El conocimiento cero computacional se obtiene exigiendo que las vistas del verificador y del simulador sean sólo computacionalmente indistinguibles , dada la cadena auxiliar. [ cita necesaria ]
Podemos aplicar estas ideas a una aplicación de criptografía más realista. Peggy quiere demostrarle a Víctor que conoce el registro discreto de un valor determinado en un grupo determinado . [11]
Por ejemplo, dado un valor , un primo grande y un generador , quiere demostrar que conoce un valor tal que , sin revelarlo . De hecho, el conocimiento de podría usarse como prueba de identidad, en el sentido de que Peggy podría tener dicho conocimiento porque eligió un valor aleatorio que no reveló a nadie, calculó y distribuyó el valor de a todos los verificadores potenciales, de modo que en un Más adelante, demostrar conocimiento de equivale a demostrar la identidad de Peggy.
El protocolo procede de la siguiente manera: en cada ronda, Peggy genera un número aleatorio , lo calcula y se lo revela a Víctor. Después de recibir , Víctor emite aleatoriamente una de las dos solicitudes siguientes: solicita que Peggy revele el valor de , o el valor de .
Víctor puede verificar cualquiera de las respuestas; si lo solicitó , podrá calcular y verificar que coincida . Si lo solicitó , podrá verificar que concuerda con esto, computando y verificando que coincide . Si Peggy realmente conoce el valor de , puede responder a cualquiera de los posibles desafíos de Víctor.
Si Peggy supiera o pudiera adivinar qué desafío va a plantear Víctor, entonces fácilmente podría engañar y convencer a Víctor de que sabe cuando no lo sabe: si sabe que Víctor va a solicitar , entonces procede normalmente: elige , calcula y le revela a Víctor; ella podrá responder al desafío de Víctor. Por otro lado, si sabe que Víctor solicitará , elige un valor aleatorio , lo calcula y se lo revela a Víctor como el valor que está esperando. Cuando Víctor la desafía a revelar , ella revela , por lo que Víctor verificará la coherencia, ya que él a su vez calculará cuál coincide , ya que Peggy multiplicó por el inverso multiplicativo modular de .
Sin embargo, si en cualquiera de los escenarios anteriores, Víctor plantea un desafío distinto al que esperaba y para el cual fabricó el resultado, entonces no podrá responder al desafío bajo el supuesto de inviabilidad de resolver el registro discreto para este grupo. Si eligió y reveló , no podrá presentar un documento válido que pase la verificación de Víctor, dado que no lo sabe . Y si eligió un valor que se presenta como , entonces tendría que responder con el registro discreto del valor que reveló, pero Peggy no conoce este registro discreto, ya que el valor C que reveló se obtuvo mediante aritmética con valores conocidos. y no calculando una potencia con un exponente conocido.
Por lo tanto, quien demuestra hacer trampa tiene una probabilidad de 0,5 de hacer trampa con éxito en una ronda. Al ejecutar un número suficientemente grande de rondas, la probabilidad de que un tramposo tenga éxito puede reducirse arbitrariamente.
Para demostrar que la prueba interactiva anterior no proporciona ningún conocimiento aparte del hecho de que Peggy conoce el valor, se pueden utilizar argumentos similares a los utilizados en la prueba anterior de integridad y solidez. Específicamente, un simulador, digamos Simon, que no conoce el valor, puede simular el intercambio entre Peggy y Victor mediante el siguiente procedimiento. En primer lugar, Simon lanza al azar una moneda justa. Si el resultado es "cabeza", elige un valor aleatorio , lo calcula y lo revela como si fuera un mensaje de Peggy a Víctor. Luego, Simon también genera un mensaje "solicita el valor de " como si lo hubiera enviado Víctor a Peggy, e inmediatamente genera el valor de como si lo hubiera enviado Peggy a Víctor. Se completa una sola ronda. Por otro lado, si el resultado del lanzamiento de la moneda es "cola", Simon elige un número aleatorio , lo calcula y lo revela como si fuera un mensaje de Peggy a Víctor. Luego Simon muestra "solicitar el valor de " como si fuera un mensaje de Víctor a Peggy. Finalmente, Simon genera el valor de como si fuera la respuesta de Peggy a Víctor. Se completa una sola ronda. Según los argumentos anteriores al demostrar la integridad y solidez, la comunicación interactiva simulada por Simon es indistinguible de la verdadera correspondencia entre Peggy y Victor. De este modo se garantiza la propiedad de conocimiento cero.
Peggy demuestra conocer el valor de x (por ejemplo, su contraseña).
El valor puede verse como el valor cifrado de . Si es verdaderamente aleatorio, distribuido equitativamente entre cero y , esto no filtra ninguna información (consulte el panel de un solo uso ).
El siguiente esquema se debe a Manuel Blum . [12]
En este escenario, Peggy conoce un ciclo hamiltoniano para un gráfico grande G. Víctor conoce G pero no el ciclo (por ejemplo, Peggy generó G y se lo reveló). Se cree que encontrar un ciclo hamiltoniano dado un gráfico grande es computacionalmente inviable, ya que se sabe que su versión de decisión correspondiente es NP-completa . Peggy demostrará que conoce el ciclo sin simplemente revelarlo (tal vez Víctor esté interesado en comprarlo pero primero quiere verificación, o tal vez Peggy sea la única que conoce esta información y le está demostrando su identidad a Víctor).
Para demostrar que Peggy conoce este ciclo hamiltoniano, ella y Víctor juegan varias rondas de un juego:
Es importante que el compromiso con el gráfico sea tal que Víctor pueda verificar, en el segundo caso, que el ciclo realmente está formado por aristas de H . Esto se puede hacer, por ejemplo, comprometiéndose con cada ventaja (o la falta de ella) por separado.
Si Peggy conoce un ciclo hamiltoniano en G , puede satisfacer fácilmente la demanda de Víctor del isomorfismo gráfico que produce H a partir de G (al que se había comprometido en el primer paso) o un ciclo hamiltoniano en H (que puede construir aplicando el isomorfismo al ciclo en G ).
Las respuestas de Peggy no revelan el ciclo hamiltoniano original en G. En cada ronda, Víctor aprenderá solo el isomorfismo de H con respecto a G o un ciclo hamiltoniano en H. Necesitaría ambas respuestas para una sola H para descubrir el ciclo en G , por lo que la información seguirá siendo desconocida mientras Peggy pueda generar una H distinta en cada ronda. Si Peggy no conoce un ciclo hamiltoniano en G , pero de alguna manera sabía de antemano qué pediría Víctor para ver cada ronda, entonces podría hacer trampa. Por ejemplo, si Peggy supiera de antemano que Víctor pediría ver el ciclo hamiltoniano en H , entonces podría generar un ciclo hamiltoniano para una gráfica no relacionada. De manera similar, si Peggy supiera de antemano que Víctor pediría ver el isomorfismo, entonces simplemente podría generar un gráfico isomórfico H (en el que tampoco conoce un ciclo hamiltoniano). Víctor podría simular el protocolo él solo (sin Peggy) porque sabe lo que pedirá ver. Por lo tanto, Víctor no obtiene información sobre el ciclo hamiltoniano en G a partir de la información revelada en cada ronda.
Si Peggy no conoce la información, puede adivinar qué pregunta hará Víctor y generar un gráfico isomorfo a G o un ciclo hamiltoniano para un gráfico no relacionado, pero como no conoce un ciclo hamiltoniano para G, no puede hacer ambas cosas. Con estas conjeturas, su probabilidad de engañar a Víctor es 2 − n , donde n es el número de rondas. Para todos los propósitos realistas, es inviablemente difícil derrotar de esta manera una prueba de conocimiento cero con un número razonable de rondas.
Se pueden definir diferentes variantes de conocimiento cero formalizando el concepto intuitivo de lo que se entiende por la salida del simulador "parecida" a la ejecución del protocolo de prueba real de las siguientes maneras:
La investigación sobre pruebas de conocimiento cero ha sido motivada por sistemas de autenticación en los que una parte quiere demostrar su identidad a una segunda parte mediante información secreta (como una contraseña), pero no quiere que la segunda parte sepa nada sobre este secreto. A esto se le llama " prueba de conocimiento de conocimiento cero ". Sin embargo, una contraseña suele ser demasiado pequeña o no lo suficientemente aleatoria para usarse en muchos esquemas de pruebas de conocimiento sin conocimiento. Una prueba de contraseña de conocimiento cero es un tipo especial de prueba de conocimiento de conocimiento cero que aborda el tamaño limitado de las contraseñas. [ cita necesaria ]
En abril de 2015, se introdujo el protocolo de pruebas una entre muchas (un protocolo Sigma ). [14] En agosto de 2021, Cloudflare , una empresa estadounidense de seguridad e infraestructura web decidió utilizar el mecanismo de prueba una entre muchas para la verificación web privada utilizando hardware de proveedor. [15]
Uno de los usos de las pruebas de conocimiento cero dentro de los protocolos criptográficos es imponer un comportamiento honesto manteniendo la privacidad. A grandes rasgos, la idea es obligar a un usuario a demostrar, mediante una prueba de conocimiento cero, que su comportamiento es correcto según el protocolo. [16] [17] Por razones de solidez, sabemos que el usuario debe actuar realmente con honestidad para poder proporcionar una prueba válida. Gracias al conocimiento cero, sabemos que el usuario no compromete la privacidad de sus secretos en el proceso de proporcionar la prueba. [ cita necesaria ]
En 2016, el Laboratorio de Física del Plasma de Princeton y la Universidad de Princeton demostraron una técnica que puede tener aplicabilidad en futuras conversaciones sobre desarme nuclear . Permitiría a los inspectores confirmar si un objeto es realmente un arma nuclear sin registrar, compartir o revelar el funcionamiento interno, que podría ser secreto. [18]
Se aplicaron pruebas de conocimiento cero en los protocolos Zerocoin y Zerocash, que culminaron en el nacimiento de Zcoin [19] (luego rebautizado como Firo en 2020) [20] y las criptomonedas Zcash en 2016. Zerocoin tiene un modelo de mezcla incorporado que no No confíe en ningún par ni en proveedores de mezcla centralizados para garantizar el anonimato. [19] Los usuarios pueden realizar transacciones en una moneda base y pueden ingresar y sacar la moneda de Zerocoins. [21] El protocolo Zerocash utiliza un modelo similar (una variante conocida como prueba de conocimiento cero no interactiva ) [22] excepto que puede ocultar el monto de la transacción, mientras que Zerocoin no puede. Dadas las importantes restricciones de los datos de transacciones en la red Zerocash, Zerocash es menos propenso a sufrir ataques de sincronización de privacidad en comparación con Zerocoin. Sin embargo, esta capa adicional de privacidad puede causar una hiperinflación potencialmente no detectada del suministro de Zerocash porque no se pueden rastrear las monedas fraudulentas. [19] [23]
En 2018, se introdujeron los Bulletproofs. Las pruebas de balas son una mejora con respecto a la prueba de conocimiento cero no interactiva donde no se necesita una configuración confiable. [24] Posteriormente se implementó en el protocolo Mimblewimble (en el que se basan las criptomonedas Grin y Beam) y en la criptomoneda Monero . [25] En 2019, Firo implementó el protocolo Sigma, que es una mejora del protocolo Zerocoin sin una configuración confiable. [26] [14] En el mismo año, Firo introdujo el protocolo Lelantus, una mejora del protocolo Sigma, donde el primero oculta el origen y el monto de una transacción. [27]
Las pruebas de conocimiento cero, por su naturaleza, pueden mejorar la privacidad en los sistemas de intercambio de identidades, que son vulnerables a violaciones de datos y robo de identidad. Cuando se integran a un sistema de identificación descentralizado, los ZKP agregan una capa adicional de cifrado en los documentos DID. [28]
Las pruebas de conocimiento cero fueron concebidas por primera vez en 1985 por Shafi Goldwasser , Silvio Micali y Charles Rackoff en su artículo "La complejidad del conocimiento de los sistemas de prueba interactivos". [16] Este artículo introdujo la jerarquía de propiedad intelectual de los sistemas de prueba interactivos ( ver sistema de prueba interactivo ) y concibió el concepto de complejidad del conocimiento , una medida de la cantidad de conocimiento sobre la prueba transferida del probador al verificador. También dieron la primera prueba de conocimiento cero para un problema concreto, el de decidir no residuos cuadráticos mod m . Junto con un artículo de László Babai y Shlomo Moran , este artículo histórico inventó sistemas de prueba interactivos, por los que los cinco autores ganaron el primer Premio Gödel en 1993.
En sus propias palabras, Goldwasser, Micali y Rackoff dicen:
De particular interés es el caso en el que este conocimiento adicional es esencialmente 0 y demostramos que es posible demostrar interactivamente que un número es cuadrático sin residuo mod m liberando 0 conocimiento adicional. Esto es sorprendente ya que no se conoce ningún algoritmo eficiente para decidir la residuosidad cuadrática mod m cuando no se da la factorización de m . Además, todas las pruebas NP conocidas para este problema exhiben la factorización prima de m . Esto indica que agregar interacción al proceso de demostración puede disminuir la cantidad de conocimiento que debe comunicarse para demostrar un teorema.
El problema cuadrático sin residuos tiene un algoritmo NP y co-NP , por lo que se encuentra en la intersección de NP y co-NP . Esto también fue cierto para varios otros problemas para los cuales posteriormente se descubrieron pruebas de conocimiento cero, como un sistema de prueba inédito de Oded Goldreich que verificaba que un módulo de dos primos no es un entero de Blum . [29]
Oded Goldreich , Silvio Micali y Avi Wigderson llevaron esto un paso más allá y demostraron que, suponiendo la existencia de un cifrado irrompible, se puede crear un sistema de prueba de conocimiento cero para el problema de coloración de gráficos NP-completo con tres colores. Dado que cada problema en NP se puede reducir eficientemente a este problema, esto significa que, bajo este supuesto, todos los problemas en NP tienen pruebas de conocimiento cero. [30] La razón de la suposición es que, como en el ejemplo anterior, sus protocolos requieren cifrado. Una condición suficiente comúnmente citada para la existencia de un cifrado indescifrable es la existencia de funciones unidireccionales , pero es posible que algunos medios físicos también puedan lograrlo.
Además de esto, también demostraron que el problema de no isomorfismo de grafos , el complemento del problema de isomorfismo de grafos , tiene una prueba de conocimiento cero. Este problema está en co-NP , pero actualmente no se sabe que esté ni en NP ni en ninguna clase práctica. De manera más general, Russell Impagliazzo y Moti Yung, así como Ben-Or et al. Continuaría demostrando que, asumiendo también funciones unidireccionales o cifrado irrompible, existen pruebas de conocimiento cero para todos los problemas en IP = PSPACE , o en otras palabras, cualquier cosa que pueda ser probada mediante un sistema de prueba interactivo puede ser probada. con cero conocimiento. [31] [32]
Como no les gustaba hacer suposiciones innecesarias, muchos teóricos buscaron una manera de eliminar la necesidad de funciones unidireccionales . Una forma de hacerlo fue con sistemas de prueba interactivos de múltiples probadores (ver sistema de prueba interactivo ), que tienen múltiples probadores independientes en lugar de uno solo, lo que permite al verificador "interrogar" a los probadores de forma aislada para evitar ser engañado. Se puede demostrar que, sin ningún supuesto de intratabilidad, todos los idiomas en NP tienen pruebas de conocimiento cero en dicho sistema. [33]
Resulta que en un entorno similar a Internet, donde se pueden ejecutar múltiples protocolos al mismo tiempo, crear pruebas de conocimiento cero es más desafiante. La línea de investigación que investiga las pruebas concurrentes de conocimiento cero fue iniciada por el trabajo de Dwork , Naor y Sahai . [34] Un desarrollo particular en este sentido ha sido el desarrollo de protocolos de prueba indistinguibles entre testigos . La propiedad de la indistinguibilidad de los testigos está relacionada con la del conocimiento cero, pero los protocolos de indistinguibilidad de los testigos no sufren los mismos problemas de ejecución concurrente. [35]
Otra variante de las pruebas de conocimiento cero son las pruebas de conocimiento cero no interactivas . Blum, Feldman y Micali demostraron que una cadena aleatoria común compartida entre el probador y el verificador es suficiente para lograr conocimiento cero computacional sin requerir interacción. [5] [6]
Los protocolos de prueba de conocimiento cero interactivos o no interactivos más populares (por ejemplo, zk-SNARK) se pueden clasificar en términos generales en las siguientes cuatro categorías: argumentos de conocimiento sucintos no interactivos (SNARK), argumentos de conocimiento escalables y transparentes (STARK), Delegación polinómica verificable (VPD) y argumentos sucintos no interactivos (SNARG). A continuación se proporciona una lista de protocolos y bibliotecas a prueba de conocimiento cero junto con comparaciones basadas en transparencia , universalidad , seguridad poscuántica plausible y paradigma de programación . [36] Un protocolo transparente es aquel que no requiere ninguna configuración confiable y utiliza aleatoriedad pública. Un protocolo universal es aquel que no requiere una configuración confiable separada para cada circuito. Finalmente, un protocolo plausiblemente poscuántico es aquel que no es susceptible a ataques conocidos que involucran algoritmos cuánticos.
{{cite book}}
: CS1 maint: location missing publisher (link){{cite book}}
: CS1 maint: location missing publisher (link)