Prueba de conocimiento cero

En criptografía , una prueba de conocimiento cero es un protocolo en el que una parte (el demostrador) puede convencer a otra parte (el verificador) de que una determinada afirmación es verdadera, sin transmitir al verificador ninguna información más allá del 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 demostrar esta posesión sin revelar esta información (o cualquier aspecto de ella). ^[2]

Teniendo en cuenta que solo se puede generar una prueba de alguna afirmación cuando se posee cierta información secreta relacionada con la afirmación, el verificador, incluso después de haberse convencido de la verdad de la afirmación, no debería, no obstante, seguir siendo incapaz de probar la afirmación ante terceros.

Las pruebas de conocimiento cero pueden ser interactivas, lo que significa que el probador y el verificador intercambian mensajes de acuerdo con algún protocolo, o no interactivas, lo que significa que el verificador se convence con un solo mensaje del probador y no se necesita otra comunicación. En el modelo estándar , se requiere interacción, excepto para pruebas triviales de problemas BPP . ^[3] En los modelos comunes de cadena aleatoria y oráculo aleatorio , existen pruebas de conocimiento cero no interactivas . La heurística Fiat-Shamir se puede utilizar para transformar ciertas pruebas interactivas de conocimiento cero en no interactivas. ^[4]^[5]^[6]

Ejemplos abstractos

La cueva de Ali Baba

Hay una historia bien 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 demostradora de la declaración, y Victor , el verificador de la declaración.

En esta historia, Peggy ha descubierto la palabra secreta que se utiliza 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 de la izquierda y la derecha desde la entrada con 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 en la cueva y grita el nombre del camino que quiere que use para regresar, A o B, elegido al azar. Si ella realmente conoce la palabra mágica, esto es fácil: abre la puerta, si es necesario, y regresa por el camino deseado.

Sin embargo, supongamos que no conocía la palabra. Entonces, solo podría regresar por el camino indicado si Víctor le dijera el nombre del mismo camino por el que ella había entrado. Como Víctor elegiría A o B al azar, ella 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 ²⁰ , o 9,56 × 10 ⁻⁷ .

Así, si Peggy aparece repetidamente en la salida que Víctor menciona, entonces él 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 la cámara grabará es, en un caso, a Víctor gritando "¡A!" y a Peggy apareciendo en A, o en el otro caso, a Víctor gritando "¡B!" y a Peggy apareciendo en B. Una grabación de este tipo sería trivial de falsificar para dos personas cualesquiera (sólo se requiere que Peggy y Víctor acuerden de antemano la secuencia de A y B que Víctor gritará). Una grabación de este tipo seguramente nunca será convincente para nadie más que para los participantes originales. De hecho, incluso una persona que estuvo presente como observador en el experimento original no debería estar convencida, ya que Víctor 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 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 cualquier persona que viera la grabación más tarde. Por lo tanto, aunque esto no le revela la palabra secreta a Víctor, sí hace posible que Víctor convenza al mundo en general de que Peggy tiene ese conocimiento, en contra de los deseos expresados por 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 que solo conoce el dueño de la moneda. Si la moneda de Víctor se comportara de esta manera, entonces 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 usar una moneda lanzada.

Peggy podría demostrarle a Víctor que conoce la palabra mágica, sin revelársela, en una sola prueba. Si tanto Víctor como Peggy van juntos a la boca de la cueva, Víctor puede ver a Peggy entrar por A y salir por B. Esto probaría con certeza que Peggy conoce la palabra mágica, sin revelársela a Víctor. Sin embargo, una tercera persona podría observar esa prueba, o Víctor podría grabarla y sería convincente para cualquiera. En otras palabras, Peggy no podría refutar esa prueba alegando que coludió con Víctor y, por lo tanto, ya no tiene control sobre quién está al tanto de su conocimiento.

Dos pelotas y el amigo daltónico

Imagina que tu amigo "Victor" es daltónico ( mientras que tú no) 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 es escéptico de que las bolas sean realmente distinguibles. Quieres demostrarle a Víctor que, de hecho, las bolas son de diferente color , pero nada más. En particular, no quieres revelar qué bola es la roja y cuál es la verde.

He aquí el sistema de prueba. Le das las dos bolas a Víctor y él las pone detrás de su espalda. A continuación, toma una de las bolas y 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 bola?" Todo este procedimiento se repite tantas veces como sea necesario.

Por supuesto, si se observan los colores de las bolas, se puede decir con certeza si las cambió o no. Por otro lado, si las bolas fueran del mismo color y, por lo tanto, indistinguibles, no habría forma de adivinar correctamente con una probabilidad superior al 50%.

Dado que la probabilidad de que hayas logrado identificar aleatoriamente cada interruptor/no interruptor es del 50%, la probabilidad de haber logrado identificar aleatoriamente todos los interruptores/no interruptores se acerca a cero ("certeza"). Si tú y tu amigo repiten esta "prueba" varias veces (por ejemplo, 20 veces), tu amigo debería convencerse ("completitud") de que las bolas son, en efecto, de diferentes colores.

La prueba anterior es de conocimiento cero porque su amigo nunca aprende qué bola es verde y cuál es roja; de hecho, no obtiene ningún conocimiento sobre cómo distinguir las bolas. ^[8]

¿Dónde está Wally?

Un ejemplo bien conocido de una prueba de conocimiento cero es el ejemplo de "¿Dónde está Wally?". En este ejemplo, el probador quiere demostrarle al verificador que sabe dónde está Wally en una página de un libro de "¿Dónde está Wally? ", sin revelar su ubicación al verificador. ^[9]

El verificador comienza tomando una gran tabla negra con un pequeño agujero en ella, del tamaño de Waldo. La tabla es 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 la está colocando el verificador. Luego, el verificador coloca la tabla sobre la página de modo que Waldo esté en el agujero. ^[9]

El verificador puede ahora mirar a través del agujero y ver a Waldo, pero no puede ver ninguna otra parte de la página. Por lo 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 una prueba de conocimiento cero.

Definición

Una prueba de conocimiento cero de alguna afirmación debe satisfacer tres propiedades:

Completitud : si la afirmación es verdadera, entonces un verificador honesto (es decir, uno que sigue el protocolo correctamente) será convencido de este hecho por un demostrador honesto.
Solidez : si la afirmación es falsa, entonces ningún verificador tramposo puede convencer a un verificador honesto de que es verdadera, excepto con alguna pequeña probabilidad.
Conocimiento cero : si la afirmación es verdadera, entonces ningún verificador aprende nada más que el hecho de que la afirmación es verdadera. En otras palabras, el simple hecho de conocer la afirmación (no el secreto) es suficiente para imaginar un escenario que muestre que el probador conoce el secreto. Esto se formaliza mostrando que cada verificador tiene algún simulador que, dada únicamente la afirmación que se va a probar (y sin acceso al probador), puede producir una transcripción que "parece" una interacción entre un probador honesto y el verificador en cuestión.

Las dos primeras son propiedades de sistemas de prueba interactivos más generales . La tercera 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 verificador tramposo sea capaz de convencer al verificador de una afirmación falsa. En otras palabras, las pruebas de conocimiento cero son "pruebas" probabilísticas en lugar de pruebas deterministas. Sin embargo, existen técnicas para reducir el error de solidez a valores insignificantemente pequeños (por ejemplo, adivinar correctamente cien o mil decisiones binarias tiene un error de solidez de 1/2 ¹⁰⁰ o 1/2 ¹⁰⁰⁰ , respectivamente. A medida que aumenta el número de bits, el error de solidez disminuye hacia cero).

Una definición formal de conocimiento cero debe utilizar algún modelo computacional, siendo el más común el de una máquina de Turing . Sean $P$ , $V$ y $S$ máquinas de Turing. Un sistema de prueba interactivo con $(P, V)$ para un lenguaje $L$ es de conocimiento cero si para cualquier verificador de tiempo polinomial probabilístico (PPT) $V̂$ existe un simulador de PPT $S$ tal que:

\forall x\in L,z\in \{0,1\}^{*},\operatorname {View} _{\hat {V}}\left[P(x)\leftrightarrow {\hat {V}}(x,z)\right]=S(x,z),

donde $View V̂ [P (x)\leftrightarrow V̂ (x, z)]$ es un registro de las interacciones entre $P (x)$ y $V (x, z)$ . El demostrador $P$ se modela como si tuviera un poder computacional ilimitado (en la práctica, $P$ suele ser una máquina de Turing probabilística ). Intuitivamente, la definición establece que un sistema de prueba interactivo $(P, V)$ es de conocimiento cero si para cualquier verificador $V̂$ existe un simulador eficiente $S$ (dependiendo de $V̂$ ) que puede reproducir la conversación entre $P$ y $V̂$ en cualquier entrada dada. La cadena auxiliar $z$ en la definición juega el papel de "conocimiento previo" (incluidas las monedas aleatorias de $V̂$ ). La definición implica que $V̂$ no puede usar ninguna cadena de conocimiento previo $z$ para extraer información de su conversación con $P$ , porque si $a S$ también se le da este conocimiento previo, entonces puede reproducir la conversación entre $V̂$ y $P$ tal como antes. ^{[ cita requerida ]}

La definición dada es la de conocimiento cero perfecto. El conocimiento cero computacional se obtiene al exigir que las vistas del verificador $V̂$ y del simulador sean solo computacionalmente indistinguibles , dada la cadena auxiliar. ^{[ cita requerida ]}

Ejemplos prácticos

Logaritmo discreto de un valor dado

Estas ideas se pueden aplicar a una aplicación criptográfica más realista. Peggy quiere demostrarle a Víctor que conoce el logaritmo discreto de un valor dado en un grupo dado . ^[11]

Por ejemplo, dado un valor $y$ , un primo grande $p$ y un generador , ella quiere probar que conoce un valor $x$ tal que $g$ $x$ $\equiv$ $y$ $(mod$ $p$ $)$ , sin revelar $x$ . De hecho, el conocimiento de $x$ podría usarse como una prueba de identidad, en el sentido de que Peggy podría tener tal conocimiento porque eligió un valor aleatorio $x$ que no reveló a nadie, calculó $y$ $=$ $g$ $x$ $mod$ $p$ y distribuyó el valor de $y$ a todos los verificadores potenciales, de modo que en un momento posterior, probar el conocimiento de $x$ es equivalente a probar la identidad como Peggy. $g$

El protocolo se desarrolla de la siguiente manera: en cada ronda, Peggy genera un número aleatorio $r$ , calcula $C = g r mod p$ y se lo revela a Víctor. Después de recibir $C$ , Víctor emite aleatoriamente una de las dos solicitudes siguientes: o bien solicita que Peggy revele el valor de $r$ o bien el valor de $(x + r) mod (p - 1)$ .

Víctor puede verificar cualquiera de las respuestas; si solicitó $r$ , puede calcular $g r mod p$ y verificar que coincide con $C.$ Si solicitó $(x + r) mod (p - 1)$ , puede verificar que $C$ es consistente con esto, calculando $g (x + r) mod (p - 1) mod p$ y verificando que coincide con $(C \cdot y) mod p$ . Si Peggy conoce de hecho el valor de $x$ , puede responder a cualquiera de los posibles desafíos de Víctor.

Si Peggy supiera o pudiera adivinar qué desafío va a lanzar Víctor, entonces podría engañar fácilmente y convencer a Víctor de que sabe $x$ cuando no es así: si sabe que Víctor va a solicitar $r$ , entonces procede normalmente: elige $r$ , calcula $C = g r mod p$ y revela $C$ a Víctor; podrá responder al desafío de Víctor. Por otro lado, si sabe que Víctor solicitará $(x + r) mod (p - 1)$ , entonces elige un valor aleatorio $r'$ , calcula $C' \equiv g r' \cdot (g x) -1 mod p$ y revela $C'$ a Víctor como el valor de $C$ que él espera. Cuando Víctor la desafía a revelar $(x + r) mod (p - 1)$ , ella revela $r'$ , para lo cual Víctor verificará la consistencia, ya que a su vez calculará $g r' mod p$ , que coincide con $C' \cdot y$ , ya que Peggy multiplicó por el inverso multiplicativo modular de $y$ .

Sin embargo, si en cualquiera de los escenarios anteriores Víctor plantea un desafío distinto del que ella esperaba y para el cual fabricó el resultado, entonces no podrá responder al desafío bajo el supuesto de inviabilidad de resolver el logaritmo discreto para este grupo. Si eligió $r$ y reveló $C = g r mod p$ , entonces no podrá producir un $(x + r) mod (p - 1)$ válido que pase la verificación de Víctor, dado que no conoce $x$ . Y si eligió un valor $r'$ que se plantea como $(x + r) mod (p - 1)$ , entonces tendría que responder con el logaritmo discreto del valor que reveló - pero Peggy no conoce este logaritmo discreto, ya que el valor $C$ que reveló se obtuvo a través de aritmética con valores conocidos, y no calculando una potencia con un exponente conocido.

Por lo tanto, un probador tramposo tiene una probabilidad de 0,5 de hacer trampa con éxito en una ronda. Al ejecutar una cantidad suficientemente grande de rondas, la probabilidad de que un probador tramposo tenga éxito puede hacerse arbitrariamente baja.

Para demostrar que la prueba interactiva anterior no proporciona ningún conocimiento aparte del hecho de que Peggy sabe $x$ , se pueden utilizar argumentos similares a los utilizados en la prueba anterior de completitud y solidez. En concreto, un simulador, digamos Simon, que no sabe $x$ , puede simular el intercambio entre Peggy y Victor mediante el siguiente procedimiento. En primer lugar, Simon lanza al azar una moneda. Si el resultado es "cara", entonces elige un valor aleatorio $r$ , calcula $C = g r mod p$ y revela $C$ como si fuera un mensaje de Peggy a Victor. A continuación, Simon también emite un mensaje "solicita el valor de $r$ " como si se lo enviara de Victor a Peggy, e inmediatamente emite el valor de $r$ como si se lo enviara de Peggy a Victor. Se completa una sola ronda. Por otro lado, si el resultado del lanzamiento de la moneda es "cruz", Simon elige un número aleatorio $r'$ , calcula $C' = g r' \cdot y -1 mod p$ y revela $C'$ como si fuera un mensaje de Peggy a Victor. Luego, Simon emite "solicita el valor de $(x + r) mod (p - 1)$ " como si fuera un mensaje de Victor a Peggy. Finalmente, Simon emite el valor de $r'$ como si fuera la respuesta de Peggy a Victor. Se completa una sola ronda. Por los argumentos anteriores al probar la completitud y solidez, la comunicación interactiva simulada por Simon es indistinguible de la correspondencia verdadera entre Peggy y Victor. Por lo tanto, la propiedad de conocimiento cero está garantizada.

Breve resumen

Peggy demuestra conocer el valor de $x$ (por ejemplo su contraseña).

Peggy y Victor están de acuerdo en un primo $p$ y un generador del grupo multiplicativo del campo $ℤ$ $p$ . $g$
Peggy calcula el valor $y = g x mod p$ y transfiere el valor a Víctor.
Los dos pasos siguientes se repiten un (gran) número de veces.
1. Peggy elige repetidamente un valor aleatorio $r \in U [0, p - 2]$ y calcula $C = g r mod p$ . Le transfiere el valor $C$ a Víctor.
2. Víctor le pide a Peggy que calcule y transfiera el valor $(x + r) mod (p - 1)$ o el valor $r$ . En el primer caso, Víctor verifica $C \cdot y \equiv g (x + r) mod (p - 1) mod p$ . En el segundo caso, verifica $C = g r mod p$ .

El valor $(x + r) mod (p - 1)$ puede verse como el valor cifrado de $x mod (p - 1)$ . Si $r$ es verdaderamente aleatorio, distribuido uniformemente entre cero y $p - 2$ , entonces esto no filtra ninguna información sobre $x$ (ver block de un solo uso ).

Ciclo hamiltoniano para un gráfico grande

El siguiente esquema se debe a Manuel Blum . ^[12]

En este escenario, Peggy conoce un ciclo hamiltoniano para un grafo grande $G.$ Victor conoce $G$ pero no el ciclo (por ejemplo, Peggy ha generado $G$ y se lo ha revelado). Se cree que encontrar un ciclo hamiltoniano dado un grafo grande es computacionalmente inviable, ya que se sabe que su versión de decisión correspondiente es NP-completa . Peggy probará que conoce el ciclo sin simplemente revelarlo (tal vez Victor esté interesado en comprarlo pero quiere la verificación primero, o tal vez Peggy sea la única que conoce esta información y esté probando su identidad a Victor).

Para demostrar que Peggy conoce este ciclo hamiltoniano, ella y Víctor juegan varias rondas de un juego:

Al comienzo de cada ronda, Peggy crea $H$ , un grafo que es isomorfo a $G$ (es decir, $H$ es igual que $G$ excepto que todos los vértices tienen nombres diferentes). Dado que es trivial traducir un ciclo hamiltoniano entre grafos isomorfos con isomorfismo conocido, si Peggy conoce un ciclo hamiltoniano para $G,$ entonces también debe conocer uno para $H$ .
Peggy se compromete con $H.$ Podría hacerlo mediante un esquema de compromiso criptográfico . Alternativamente, podría numerar los vértices de $H.$ A continuación, para cada arista de $H$ , en un pequeño trozo de papel, escribe los dos vértices que la arista une. Luego, pone todos estos trozos de papel boca abajo sobre una mesa. El propósito de este compromiso es que Peggy no pueda cambiar $H$ mientras que, al mismo tiempo, Victor no tenga información sobre $H.$
Luego, Víctor elige al azar una de dos preguntas para hacerle a Peggy. Puede pedirle que muestre el isomorfismo entre $H$ y $G$ (ver el problema de isomorfismo de grafos ) o puede pedirle que muestre un ciclo hamiltoniano en $H.$
Si se le pide a Peggy que demuestre que los dos gráficos son isomorfos, entonces primero descubre todo $H$ (por ejemplo, dando vuelta todos los papeles que puso sobre la mesa) y luego proporciona las traslaciones de vértices que asignan $G$ a $H.$ Víctor puede verificar que, de hecho, son isomorfos.
Si se le pide a Peggy que demuestre que conoce un ciclo hamiltoniano en $H$ , entonces traslada su ciclo hamiltoniano en $G$ a $H$ y solo descubre las aristas del ciclo hamiltoniano. Es decir, Peggy solo da vuelta exactamente $| V (G) |$ de los trozos de papel que corresponden a las aristas del ciclo hamiltoniano, mientras que deja el resto boca abajo. Esto es suficiente para que Víctor compruebe que $H$ efectivamente contiene un ciclo hamiltoniano.

Es importante que el compromiso con el grafo sea tal que Víctor pueda verificar, en el segundo caso, que el ciclo está realmente formado por aristas desde $H.$ Esto se puede hacer, por ejemplo, comprometiéndose con cada arista (o falta de ella) por separado.

Lo completo

Si Peggy conoce un ciclo hamiltoniano en $G$ , entonces puede satisfacer fácilmente la demanda de Víctor de un isomorfismo gráfico que produzca $H$ a partir de $G$ (al que se había comprometido en el primer paso) o de un ciclo hamiltoniano en $H$ (que puede construir aplicando el isomorfismo al ciclo en $G$ ).

Conocimiento cero

Las respuestas de Peggy no revelan el ciclo hamiltoniano original en $G.$ En cada ronda, Víctor aprenderá solo el isomorfismo de $H 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 permanece desconocida mientras Peggy pueda generar una $H$ distinta en cada ronda. Si Peggy no sabe de un ciclo hamiltoniano en $G$ , pero de alguna manera supiera de antemano lo que Víctor pediría ver en 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 un grafo no relacionado. De manera similar, si Peggy supiera de antemano que Víctor pediría ver el isomorfismo, entonces podría simplemente generar un grafo isomorfo $H$ (en el que tampoco conoce un ciclo hamiltoniano). Víctor podría simular el protocolo por sí mismo (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.

Solvencia

Si Peggy no conoce la información, entonces puede adivinar qué pregunta hará Víctor y generar un grafo isomorfo a $G$ o un ciclo hamiltoniano para un grafo no relacionado, pero como no conoce un ciclo hamiltoniano para $G$ , no puede hacer ambas cosas. Con esta suposición, 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 increíblemente difícil derrotar una prueba de conocimiento cero con un número razonable de rondas de esta manera.

Variantes del conocimiento cero

Se pueden definir diferentes variantes del conocimiento cero formalizando el concepto intuitivo de lo que se entiende por que la salida del simulador "se parece" a la ejecución del protocolo de prueba real de las siguientes maneras:

Hablamos de conocimiento cero perfecto si las distribuciones producidas por el simulador y el protocolo de prueba se distribuyen exactamente de la misma manera. Este es, por ejemplo, el caso del primer ejemplo anterior.
El conocimiento estadístico cero ^[13] significa que las distribuciones no son necesariamente exactamente iguales, pero son estadísticamente cercanas , lo que significa que su diferencia estadística es una función insignificante .
Hablamos de conocimiento computacional cero si ningún algoritmo eficiente puede distinguir las dos distribuciones.

Tipos de conocimiento cero

Existen varios tipos de pruebas de conocimiento cero:

Prueba de conocimiento : el conocimiento está oculto en el exponente como en el ejemplo que se muestra arriba.
Prueba indistinguible de los testigos : los verificadores no pueden saber qué testigo se utiliza para producir la prueba.

Los esquemas de prueba de conocimiento cero se pueden construir a partir de varias primitivas criptográficas, como la criptografía basada en hash , la criptografía basada en emparejamiento , el cálculo multipartito o la criptografía basada en celosía .

Aplicaciones

Sistemas de autenticación

La investigación en 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 conozca nada sobre este secreto. Esto se llama " prueba de conocimiento de conocimiento cero ". Sin embargo, una contraseña suele ser demasiado pequeña o insuficientemente aleatoria para ser utilizada en muchos esquemas de pruebas de conocimiento de conocimiento cero. 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 requerida ]}

En abril de 2015, se introdujo el protocolo de pruebas uno de muchos (un protocolo Sigma ). ^[14] En agosto de 2021, Cloudflare , una empresa estadounidense de seguridad e infraestructura web, decidió utilizar el mecanismo de pruebas uno de muchos para la verificación web privada utilizando hardware del proveedor. ^[15]

Comportamiento ético

Uno de los usos de las pruebas de conocimiento cero dentro de los protocolos criptográficos es imponer un comportamiento honesto manteniendo la privacidad. En líneas generales, la idea es obligar a un usuario a demostrar, utilizando una prueba de conocimiento cero, que su comportamiento es correcto de acuerdo con el protocolo. ^[16]^[17] Debido a la solidez, sabemos que el usuario debe actuar realmente honestamente para poder proporcionar una prueba válida. Debido al conocimiento cero, sabemos que el usuario no compromete la privacidad de sus secretos en el proceso de proporcionar la prueba. ^{[ cita requerida ]}

Desarme nuclear

En 2016, el Laboratorio de Física del Plasma de Princeton y la Universidad de Princeton demostraron una técnica que podría tener aplicación en futuras conversaciones sobre desarme nuclear . Permitiría a los inspectores confirmar si un objeto es o no un arma nuclear sin registrar, compartir o revelar su funcionamiento interno, que podría ser secreto. ^[18]

Cadenas de bloques

Las pruebas de conocimiento cero se aplicaron en los protocolos Zerocoin y Zerocash, que culminaron en el nacimiento de las criptomonedas Zcoin ^[19] (posteriormente rebautizada como Firo en 2020) ^[20] y Zcash en 2016. Zerocoin tiene un modelo de mezcla incorporado que no confía en ningún par o proveedor de mezcla centralizado para garantizar el anonimato. ^[19] Los usuarios pueden realizar transacciones en una moneda base y pueden hacer circular la moneda dentro y fuera 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 restricciones significativas de los datos de transacción en la red Zerocash, Zerocash es menos propenso a 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 de la oferta de Zerocash porque las monedas fraudulentas no pueden rastrearse. ^[19]^[23]

En 2018, se introdujeron las Bulletproofs. Las Bulletproofs son una mejora de las pruebas de conocimiento cero no interactivas donde no se necesita una configuración confiable. ^[24] Más tarde se implementó en el protocolo Mimblewimble (en el que se basan las criptomonedas Grin y Beam) y la criptomoneda Monero . ^[25] En 2019, Firo implementó el protocolo Sigma, que es una mejora del protocolo Zerocoin sin 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]

Identificadores descentralizados

Las pruebas de conocimiento cero, por su naturaleza, pueden mejorar la privacidad en los sistemas de intercambio de identidad, que son vulnerables a las violaciones de datos y al robo de identidad. Cuando se integran a un sistema de identificación descentralizado, las pruebas de conocimiento cero añaden una capa adicional de cifrado a los documentos DID. ^[28]

Historia

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 IP 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 residuos no cuadráticos mod m . Junto con un artículo de László Babai y Shlomo Moran , este artículo histórico inventó los sistemas de prueba interactivos, por los cuales 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 donde este conocimiento adicional es esencialmente 0 y mostramos que [es] posible probar interactivamente que un número es residuo cuadrático no mod m liberando 0 conocimiento adicional. Esto es sorprendente ya que no se conoce ningún algoritmo eficiente para decidir 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 prueba puede disminuir la cantidad de conocimiento que debe comunicarse para probar un teorema.

El problema de los residuos cuadráticos no complejos tiene un algoritmo NP y uno co-NP , y por lo tanto se encuentra en la intersección de NP y co-NP . Esto también fue cierto en el caso de varios otros problemas para los que se descubrieron posteriormente pruebas de conocimiento cero, como un sistema de pruebas no publicado de Oded Goldreich que verifica 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á, mostrando que, asumiendo la existencia de un cifrado irrompible, se puede crear un sistema de prueba de conocimiento cero para el problema de coloración de grafos NP-completos 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 para el supuesto es que, como en el ejemplo anterior, sus protocolos requieren cifrado. Una condición suficiente citada comúnmente para la existencia de cifrado irrompible es la existencia de funciones unidireccionales , pero es concebible 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é 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ían demostrando que, también asumiendo 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 probarse mediante un sistema de prueba interactivo puede probarse con conocimiento cero. ^[31]^[32]

Muchos teóricos, que no querían hacer suposiciones innecesarias, buscaron una forma de eliminar la necesidad de funciones unidireccionales . Una forma de hacerlo fue con sistemas de prueba interactivos con múltiples probadores (ver sistema de prueba interactivo ), que tienen múltiples probadores independientes en lugar de solo uno, lo que permite al verificador "interrogar" a los probadores de forma aislada para evitar ser engañado. Se puede demostrar que, sin ninguna suposición de intratabilidad, todos los lenguajes en NP tienen pruebas de conocimiento cero en un sistema de este tipo. ^[33]

Resulta que, en un entorno similar a Internet, donde se pueden ejecutar varios protocolos simultáneamente, la creación de pruebas de conocimiento cero es más desafiante. La línea de investigación que investiga las pruebas de conocimiento cero concurrentes fue iniciada por el trabajo de Dwork , Naor y Sahai . ^[34] Un desarrollo particular en esta línea ha sido el desarrollo de protocolos de prueba indistinguibles de testigos . La propiedad de indistinguibilidad de testigos está relacionada con la del conocimiento cero, pero los protocolos indistinguibles de 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 un conocimiento cero computacional sin requerir interacción. ^[5]^[6]

Protocolos de prueba de conocimiento cero

Los protocolos de prueba de conocimiento cero interactivos o no interactivos más populares (por ejemplo, zk-SNARK) se pueden categorizar ampliamente en las siguientes cuatro categorías: Argumentos de conocimiento no interactivos sucintos (SNARK), Argumentos de conocimiento transparentes escalables (STARK), Delegación polinomial verificable (VPD) y Argumentos no interactivos sucintos (SNARG). A continuación, se proporciona una lista de protocolos y bibliotecas de prueba de conocimiento cero junto con comparaciones basadas en transparencia , universalidad , seguridad postcuántica plausible y paradigma de programación . ^[36] Un protocolo transparente es uno que no requiere ninguna configuración confiable y utiliza aleatoriedad pública. Un protocolo universal es uno que no requiere una configuración confiable separada para cada circuito. Finalmente, un protocolo postcuántico plausible es uno que no es susceptible a ataques conocidos que involucran algoritmos cuánticos.

Véase también

Enlaces externos

El informático Amit Sahai explica la prueba de conocimiento cero en cinco niveles de dificultad en YouTube

Referencias

^ Aad, Imad (2023), Mulder, Valentin; Mermoud, Alain; Lenders, Vincent; Tellenbach, Bernhard (eds.), "Prueba de conocimiento cero", Tendencias en protección de datos y tecnologías de cifrado , Cham: Springer Nature Switzerland, págs. 25-30, doi : 10.1007/978-3-031-33386-6_6 , ISBN 978-3-031-33386-6
^ Goldreich, Oded (2001). Fundamentos de criptografía, volumen I. Cambridge University Press. pág. 184. doi :10.1017/CBO9780511546891. ISBN 9780511546891.
^ Goldreich, Oded (2001). Fundamentos de criptografía, volumen I. Cambridge University Press. pág. 247. doi :10.1017/CBO9780511546891. ISBN 9780511546891.
^ Goldreich, Oded (2001). Fundamentos de criptografía, volumen I. Cambridge University Press. pág. 299. doi :10.1017/CBO9780511546891. ISBN 9780511546891.
^ ab Blum, Manuel; Feldman, Paul; Micali, Silvio (1988). "Conocimiento cero no interactivo y sus aplicaciones". Actas del vigésimo simposio anual de la ACM sobre teoría de la computación - STOC '88 (PDF) . pp. 103–112. doi :10.1145/62212.62222. ISBN 978-0897912648. S2CID 7282320. Archivado (PDF) del original el 14 de diciembre de 2018 . Consultado el 2 de junio de 2022 .
^ ab Wu, Huixin; Wang, Feng (2014). "Un estudio de sistemas de prueba de conocimiento cero no interactivos y sus aplicaciones". The Scientific World Journal . 2014 : 560484. doi : 10.1155/2014/560484 . PMC 4032740 . PMID 24883407.
^ Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). "Cómo explicar los protocolos de conocimiento cero a sus hijos". Avances en criptología: actas de CRYPTO' 89 (PDF) . Apuntes de clase en informática. Vol. 435. págs. 628–631. doi :10.1007/0-387-34805-0_60. ISBN 978-0-387-97317-3.
^ Chalkias, Konstantinos. "Demuestre cómo funcionan las pruebas de conocimiento cero sin usar matemáticas". CordaCon 2017. Consultado el 13 de septiembre de 2017 .
^ abc Murtagh, Jack (1 de julio de 2023). "¿Dónde está Wally? Cómo demostrar matemáticamente que lo encontraste sin revelar dónde está". Scientific American . Consultado el 2 de octubre de 2023 .
^ Feige, Uriel; Fiat, Amos; Shamir, Adi (1 de junio de 1988). "Pruebas de identidad de conocimiento cero". Revista de criptología . 1 (2): 77–94. doi : 10.1007/BF02351717 . ISSN 1432-1378. S2CID 2950602.
^ Chaum, David; Evertse, Jan-Hendrik; van de Graaf, Jeroen (1988). "Un protocolo mejorado para demostrar la posesión de logaritmos discretos y algunas generalizaciones". Avances en criptología: EUROCRYPT '87 . Apuntes de conferencias sobre informática. vol. 304, págs. 127-141. doi :10.1007/3-540-39118-5_13. ISBN 978-3-540-19102-5.
^ Blum, Manuel (1986). «Cómo demostrar un teorema de modo que nadie más pueda afirmarlo» (PDF) . Actas del ICM : 1444–1451. CiteSeerX 10.1.1.469.9048 . Archivado (PDF) desde el original el 3 de enero de 2023.
^ Sahai, Amit; Vadhan, Salil (1 de marzo de 2003). "Un problema completo para el conocimiento estadístico cero" (PDF) . Revista de la ACM . 50 (2): 196–249. CiteSeerX 10.1.1.4.3957 . doi :10.1145/636865.636868. S2CID 218593855. Archivado (PDF) desde el original el 25 de junio de 2015.
^ ab Groth, J; Kohlweiss, M (14 de abril de 2015). "Una prueba entre muchas: o cómo filtrar un secreto y gastar una moneda". Avances en criptología - EUROCRYPT 2015. Apuntes de clase en informática. Vol. 9057. Berlín, Heidelberg: EUROCRYPT 2015. págs. 253–280. doi :10.1007/978-3-662-46803-6_9. hdl : 20.500.11820/f6ec5d8f-cfda-4f56-9bd0-d9222b8d9a43 . ISBN . 978-3-662-46802-9. Número de identificación del sujeto 16708805.
^ "Presentación de pruebas de conocimiento cero para la certificación web privada con hardware de múltiples proveedores". El blog de Cloudflare . 2021-08-12 . Consultado el 2021-08-18 .
^ ab Goldwasser, S.; Micali, S.; Rackoff, C. (1989), "La complejidad del conocimiento de los sistemas de prueba interactivos" (PDF) , SIAM Journal on Computing , 18 (1): 186–208, doi :10.1137/0218012, ISSN 1095-7111
^ Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 de octubre de 2020). "¿Es práctico el paradigma GMW clásico? El caso de 2PC activamente seguro no interactivo". Actas de la Conferencia ACM SIGSAC de 2020 sobre seguridad informática y de las comunicaciones . CCS '20. Evento virtual, EE. UU.: Association for Computing Machinery. págs. 1591–1605. doi :10.1145/3372297.3423366. ISBN . 978-1-4503-7089-9. Número de identificación del sujeto 226228208.
^ "PPPL y Princeton demuestran una técnica novedosa que podría tener aplicación en futuras conversaciones sobre desarme nuclear - Princeton Plasma Physics Lab" (Laboratorio de Física del Plasma de Princeton). www.pppl.gov . Archivado desde el original el 3 de julio de 2017.
^ abc Hellwig, Daniel; Karlic, Goran; Huchzermeier, Arnd (3 de mayo de 2020). "Privacidad y anonimato". Construye tu propia cadena de bloques . Gestión para profesionales. SpringerLink. p. 112. doi :10.1007/978-3-030-40142-9_5. ISBN 9783030401429. S2CID 219058406 . Consultado el 3 de diciembre de 2020 .
^ Hurst, Samantha (28 de octubre de 2020). «Zcoin anuncia un cambio de marca con un nuevo nombre y símbolo "Firo"». Crowdfund Insider. Archivado desde el original el 1 de noviembre de 2020. Consultado el 4 de noviembre de 2020 .
^ Bonneau, J; Miller, A; Clark, J; Narayanan, A (2015). "SoK: Perspectivas de investigación y desafíos para Bitcoin y las criptomonedas". Simposio IEEE sobre seguridad y privacidad de 2015. San José, California. págs. 104–121. doi :10.1109/SP.2015.14. ISBN 978-1-4673-6949-7.S2CID 549362 .{{cite book}}: CS1 maint: location missing publisher (link)
^ Ben-Sasson, Eli; Chiesa, Alessandro; Garman, Christina; Green, Matthew; Miers, Ian; Tromer, Eran; Virza, Madars (18 de mayo de 2014). «Zerocash: pagos anónimos descentralizados desde Bitcoin» (PDF) . IEEE . Consultado el 26 de enero de 2016 .
^ Orcutt, Mike. "Un truco criptográfico alucinante promete convertir las cadenas de bloques en algo común". MIT Technology Review . Consultado el 18 de diciembre de 2017 .
^ ab Bünz, B; Bootle, D; Boneh, A (2018). "Bulletproofs: Short Proofs for Confidential Transactions and More" (Pruebas a prueba de balas: pruebas breves para transacciones confidenciales y más). Simposio IEEE sobre seguridad y privacidad de 2018 (SP) . San Francisco, California. págs. 315–334. doi : 10.1109/SP.2018.00020 . ISBN. 978-1-5386-4353-2. Número de identificación del sujeto 3337741.{{cite book}}: CS1 maint: location missing publisher (link)
^ Odendaal, Hansie; Sharrock, Cayle; Heerden, SW. "Bulletproofs and Mimblewimble". Tari Labs University. Archivado desde el original el 29 de septiembre de 2020. Consultado el 3 de diciembre de 2020 .
^ Andrew, Munro (30 de julio de 2019). «La criptomoneda Zcoin presenta pruebas de conocimiento cero sin una configuración confiable». Finder Australia. Archivado desde el original el 30 de julio de 2019. Consultado el 30 de julio de 2019 .
^ Aram, Jivanyan (7 de abril de 2019). "Lelantus: Hacia la confidencialidad y el anonimato de las transacciones de blockchain a partir de suposiciones estándar". Archivo de ePrints de criptología (informe 373) . Consultado el 14 de abril de 2019 .
^ Zhou, Lu; Diro, Abebe; Saini, Akanksha; Kaisar, Shahriar; Hiep, Pham Cong (1 de febrero de 2024). "Aprovechamiento de pruebas de conocimiento cero para el intercambio de identidad basado en blockchain: un estudio de avances, desafíos y oportunidades". Revista de seguridad de la información y aplicaciones . 80 : 103678. doi : 10.1016/j.jisa.2023.103678 . ISSN 2214-2126.
^ Goldreich, Oded (1985). "Una prueba de conocimiento cero de que un módulo de dos primos no es un entero de Blum". Manuscrito inédito .
^ Goldreich, Oded; Micali, Silvio; Wigderson, Avi (1991). "Pruebas que no producen nada más que su validez". Revista de la ACM . 38 (3): 690–728. CiteSeerX 10.1.1.420.1478 . doi :10.1145/116825.116852. S2CID 2389804.
^ Russell Impagliazzo, Moti Yung: Cálculos directos de conocimiento mínimo. CRYPTO 1987: 40-51
^ Ben-Or, Michael; Goldreich, Oded; Goldwasser, Shafi; Hastad, Johan; Kilian, Joe; Micali, Silvio; Rogaway, Phillip (1990). "Todo lo que se puede demostrar se puede demostrar en el estado de conocimiento cero". En Goldwasser, S. (ed.). Avances en criptología – CRYPTO '88 . Apuntes de clase en informática. Vol. 403. Springer-Verlag. págs. 37–56.
^ Ben-or, M.; Goldwasser, Shafi; Kilian, J.; Wigderson, A. (1988). "Pruebas interactivas con múltiples probadores: cómo eliminar los supuestos de intransigencia" (PDF) . Actas del 20.º Simposio ACM sobre teoría de la computación : 113–121.
^ Dtrabajo, Cynthia; Naor, Moni; Sahai, Amit (2004). "Conocimiento cero concurrente". Revista de la ACM . 51 (6): 851–898. CiteSeerX 10.1.1.43.716 . doi :10.1145/1039488.1039489. S2CID 52827731.
^ Feige, Uriel; Shamir, Adi (1990). "Protocolos de indistinguibilidad de testigos y de ocultación de testigos". Actas del vigésimo segundo simposio anual de la ACM sobre teoría de la computación - STOC '90 . pp. 416–426. CiteSeerX 10.1.1.73.3911 . doi :10.1145/100216.100272. ISBN . 978-0897913614.S2CID 11146395 .
^ ab Mouris, Dimitris; Tsoutsos, Nektarios Georgios (2021). "Zilch: un marco para implementar pruebas transparentes de conocimiento cero". Transacciones IEEE sobre seguridad y análisis forense de la información . 16 : 3269–3284. doi :10.1109/TIFS.2021.3074869. ISSN 1556-6021. S2CID 222069813.
^ Parno, B.; Howell, J.; Gentry, C.; Raykova, M. (mayo de 2013). "Pinocho: computación verificable casi práctica". Simposio IEEE sobre seguridad y privacidad de 2013. págs. 238–252. doi :10.1109/SP.2013.47. ISBN 978-0-7695-4977-4.S2CID1155080 .
^ Costello, Craig; Fournet, Cedric; Howell, Jon; Kohlweiss, Markulf; Kreuter, Benjamin; Naehrig, Michael; Parno, Bryan; Zahur, Samee (mayo de 2015). "Geppetto: computación verificable versátil". Simposio IEEE sobre seguridad y privacidad de 2015. págs. 253–270. doi :10.1109/SP.2015.23. hdl : 20.500.11820/37920e55-65aa-4a42-b678-ef5902a5dd45 . ISBN . 978-1-4673-6949-7. Número de identificación del sujeto 3343426.
^ Ben-Sasson, Eli; Chiesa, Alessandro; Genkin, Daniel; Tromer, Eran; Virza, Madars (2013). "SNARKs para C: Verificación de ejecuciones de programas de forma sucinta y sin conocimiento". Avances en criptología – CRYPTO 2013. Apuntes de clase en informática. Vol. 8043. págs. 90–108. doi :10.1007/978-3-642-40084-1_6. hdl : 1721.1/87953 . ISBN. 978-3-642-40083-4.
^ Wahby, Riad S.; Setty, Srinath; Ren, Zuocheng; Blumberg, Andrew J.; Walfish, Michael (2015). "Flujo de control y RAM eficiente en computación subcontratada verificable". Actas del Simposio sobre seguridad de sistemas distribuidos y redes de 2015. doi :10.14722/ndss.2015.23097. ISBN 978-1-891562-38-9.
^ Eberhardt, Jacob; Tai, Stefan (julio de 2018). "ZoKrates: cálculos escalables fuera de la cadena que preservan la privacidad". Conferencia internacional IEEE de 2018 sobre Internet de las cosas (IThings) e IEEE Green Computing and Communications (GreenCom) e IEEE Cyber, Physical and Social Computing (CPSCom) e IEEE Smart Data (SmartData) . págs. 1084–1091. doi :10.1109/Cybermatics_2018.2018.00199. ISBN . 978-1-5386-7975-3.S2CID 49473237 .
^ Kosba, Ahmed; Papamanthou, Charalampos; Shi, Elaine (mayo de 2018). "XJsnark: un marco para la computación verificable y eficiente". Simposio IEEE sobre seguridad y privacidad de 2018 (SP) . págs. 944–961. doi : 10.1109/SP.2018.00018 . ISBN . 978-1-5386-4353-2.
^ Zhang, Yupeng; Genkin, Daniel; Katz, Jonathan; Papadopoulos, Dimitrios; Papamanthou, Charalampos (mayo de 2018). "VRAM: RAM verificable más rápida con preprocesamiento independiente del programa". Simposio IEEE sobre seguridad y privacidad de 2018 (SP) . págs. 908–925. doi : 10.1109/SP.2018.00013 . ISBN . 978-1-5386-4353-2.
^ Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars (20 de agosto de 2014). "Conocimiento cero sucinto y no interactivo para una arquitectura de von Neumann". Actas del 23.º Simposio de la Conferencia USENIX sobre Seguridad . Asociación USENIX: 781–796. ISBN 9781931971157.
^ Kosba, Ahmed; Papadopoulos, Dimitrios; Papamanthou, Charalampos; Song, Dawn (2020). "MIRAGE: argumentos sucintos a favor de algoritmos aleatorios con aplicaciones a zk-SNARKs universales". Archivo de ePrints de criptología .
^ Maller, Mary; Bowe, Sean; Kohlweiss, Markulf; Meiklejohn, Sarah (6 de noviembre de 2019). "Sonic: SNARK de conocimiento cero a partir de cadenas de referencia estructuradas universales y actualizables de tamaño lineal". Actas de la Conferencia ACM SIGSAC de 2019 sobre seguridad informática y de las comunicaciones. Association for Computing Machinery. págs. 2111–2128. doi :10.1145/3319535.3339817. hdl : 20.500.11820/739b94f1-54f0-4ec3-9644-3c95eea1e8f5 . ISBN . 9781450367479. Número de identificación del sujeto 242772913.
^ Chiesa, Alessandro; Hu, Yuncong; Maller, Mary; Mishra, Pratyush; Vesely, Noah; Ward, Nicholas (2020). "Marlin: preprocesamiento de zkSNARK con SRS universal y actualizable". Avances en criptología – EUROCRYPT 2020 . Apuntes de clase en informática. Vol. 12105. Springer International Publishing. págs. 738–768. doi :10.1007/978-3-030-45721-1_26. ISBN 978-3-030-45720-4. Número de identificación del sujeto 204772154.
^ Gabizon, Ariel; Williamson, Zachary J.; Ciobotaru, Oana (2019). "PLONK: Permutaciones sobre bases de Lagrange para argumentos ecuménicos no interactivos de conocimiento". Archivo de ePrints de criptología .
^ Bünz, Benedikt; Fisch, Ben; Szepieniec, Alan (2020). "SNARK transparentes de compiladores DARK". Avances en criptología – EUROCRYPT 2020. Apuntes de clase en informática. Vol. 12105. Springer International Publishing. págs. 677–706. doi :10.1007/978-3-030-45721-1_24. ISBN 978-3-030-45720-4. Número de identificación del sujeto 204892714.
^ Wahby, Riad S.; Tzialla, Ioanna; Shelat, Abhi; Thaler, Justin; Walfish, Michael (mayo de 2018). "ZkSNARKs doblemente eficientes sin configuración confiable". Simposio IEEE sobre seguridad y privacidad de 2018 (SP) . págs. 926–943. doi : 10.1109/SP.2018.00060 . ISBN . 978-1-5386-4353-2.
^ Bowe, Sean; Grigg, Jack; Hopwood, Daira (2019). "Composición de pruebas recursivas sin una configuración confiable". Archivo de ePrints de criptología .
^ Zhang, Jiaheng; Xie, Tiancheng; Zhang, Yupeng; Song, Dawn (mayo de 2020). "Delegación polinomial transparente y sus aplicaciones a la prueba de conocimiento cero". Simposio IEEE sobre seguridad y privacidad de 2020 (SP) . págs. 859–876. doi : 10.1109/SP40000.2020.00052 . ISBN . 978-1-7281-3497-0.
^ Ames, Scott; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 de octubre de 2017). "Ligero". Actas de la Conferencia ACM SIGSAC de 2017 sobre seguridad informática y de las comunicaciones . Association for Computing Machinery. págs. 2087–2104. doi :10.1145/3133956.3134104. ISBN 9781450349468.S2CID5348527 .
^ Ben-Sasson, Eli; Chiesa, Alessandro; Riabzev, Michael; Spooner, Nicholas; Virza, Madars; Ward, Nicholas P. (2019). "Aurora: argumentos sucintos y transparentes a favor de R1CS". Avances en criptología – EUROCRYPT 2019. Apuntes de clase en informática. Vol. 11476. Springer International Publishing. págs. 103–128. doi :10.1007/978-3-030-17653-2_4. ISBN 978-3-030-17652-5. Número de identificación del sujeto 52832327.
^ Ben-Sasson, Eli; Bentov, Iddo; Horesh, Yinon; Riabzev, Michael (2019). "Conocimiento cero escalable sin configuración de confianza". Avances en criptología – CRYPTO 2019. Apuntes de clase en informática. Vol. 11694. Springer International Publishing. págs. 701–732. doi :10.1007/978-3-030-26954-8_23. ISBN 978-3-030-26953-1.S2CID 199501907 .