Prueba de conocimiento cero

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 mero hecho de la verdad de la afirmación. ^[1] La intuición que subyace a las pruebas de conocimiento cero es que es trivial probar la posesión de cierta información simplemente revelándola; el desafío es probar esta posesión sin revelar la información ni ningún aspecto de la misma. ^[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 demostrar la verdad de la afirmación. declaración a 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 ).

Ejemplos abstractos

La cueva de Ali Babá

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 ²⁰ , o 9,56 × 10 ⁻⁷ .

Por lo tanto, si Peggy aparece repetidamente en la salida que Víctor nombra, 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 registra 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 puede 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 es consciente de su conocimiento.

Dos pelotas y el amigo daltónico

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 lo 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]

Dónde está Waldo

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.

Definición

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

Integridad : si la afirmación es verdadera, un verificador honesto (es decir, uno que sigue correctamente el protocolo) quedará convencido de este hecho por un probador honesto.
Solidez : si la afirmación es falsa, ningún probador tramposo puede convencer a un verificador honesto de que es verdadera, excepto con una pequeña probabilidad.
Conocimiento cero : si la afirmación es verdadera, ningún verificador aprende nada más que el hecho de que la afirmación es verdadera. En otras palabras, simplemente conocer la afirmación (no el secreto) es suficiente para imaginar un escenario que demuestre que quien lo demuestra conoce el secreto. Esto se formaliza mostrando que cada verificador tiene algún simulador que, dada sólo la afirmación que se debe 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 . 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). $1/2^{100}$ $1/2^{1000}$

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 $P$ , $V$ y $S$ máquinas de Turing. Un sistema de prueba interactivo para un lenguaje $L$ tiene conocimiento cero si para cualquier verificador de tiempo polinómico probabilístico (PPT) existe un simulador de PPT $S$ tal que: $(P,V)$ ${\hat {V}}$

\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 hay un registro de las interacciones entre y . Se modela que el demostrador $P tiene un poder de cálculo ilimitado (en la práctica,$ $P$ 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 $S$ (dependiendo de ) que pueda reproducir la conversación entre $P$ y cualquier entrada dada. La cadena auxiliar $z$ 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 $z$ para extraer información de su conversación con $P$ , porque si $S$ también recibe este conocimiento previo, entonces puede reproducir la conversación entre P y $P$ tal como antes. ^[^{cita necesaria}^] $\operatorname {View} _{\hat {V}}\left[P(x)\leftrightarrow {\hat {V}}(x,z)\right]$ $P(x)$ ${\hat {V}}(x,z)$ $(P,V)$ ${\hat {V}}$ ${\hat {V}}$ ${\hat {V}}$ ${\hat {V}}$ ${\hat {V}}$ ${\hat {V}}$

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 solo sean indistinguibles computacionalmente , dada la cadena auxiliar. ^[^{cita necesaria}^] ${\hat {V}}$

Ejemplos prácticos

Registro discreto de un valor dado

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. $y$ $p$ $g$ $x$ $g^{x}{\bmod {p}}=y$ $x$ $x$ $x$ $y=g^{x}{\bmod {p}}$ $y$ $x$

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 . $r$ $C=g^{r}{\bmod {p}}$ $C$ $r$ $(x+r){\bmod {(p-1)}}$

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. $r$ $g^{r}{\bmod {p}}$ $C$ $(x+r){\bmod {(p-1)}}$ $C$ $g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}$ $(C\cdot y){\bmod {p}}$ $x$

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 . $x$ $r$ $r$ $C=g^{r}{\bmod {p}}$ $C$ $(x+r){\bmod {(p-1)}}$ $r'$ $C'=g^{r'}\cdot \left(g^{x}\right)^{-1}{\bmod {p}}$ $C'$ $C$ $(x+r){\bmod {(p-1)}}$ $r'$ $g^{r'}{\bmod {p}}$ $C'\cdot y$ $y$

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. $r$ $C=g^{r}{\bmod {p}}$ $(x+r){\bmod {(p-1)}}$ $x$ $r'$ $(x+r){\bmod {(p-1)}}$

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. $x$ $x$ $r$ $C=g^{r}{\bmod {p}}$ $C$ $r$ $r$ $r'$ $C'=g^{r'}\cdot \left(y\right)^{-1}{\bmod {p}}$ $C'$ $(x+r){\bmod {(p-1)}}$ $r'$

Breve resumen

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

Peggy y Victor se ponen de acuerdo sobre un primo y un generador del grupo multiplicativo del campo . $p$ $g$ $\mathbb {Z} _{p}$
Peggy calcula el valor y se lo transfiere a Víctor. $y=g^{x}{\bmod {p}}$
Los dos pasos siguientes se repiten un (gran) número de veces.
1. Peggy elige repetidamente un valor aleatorio y lo calcula . Ella transfiere el valor a Víctor. $r\in U[0,p-2]$ $C=g^{r}{\bmod {p}}$ $C$
2. Victor le pide a Peggy que calcule y transfiera el valor o el valor . En el primer caso Víctor lo comprueba . En el segundo caso lo verifica . $(x+r){\bmod {(p-1)}}$ $r$ $(C\cdot y){\bmod {p}}\equiv g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}$ $C\equiv g^{r}{\bmod {p}}$

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 ). $(x+r){\bmod {(}}p-1)$ $x{\bmod {(}}p-1)$ $r$ $(p-2)$ $x$

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 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:

Al comienzo de cada ronda, Peggy crea $H$ , un gráfico que es isomorfo a $G$ (es decir, $H$ es igual a $G$ excepto que todos los vértices tienen nombres diferentes). Dado que es trivial traducir un ciclo hamiltoniano entre gráficos isomórficos con isomorfismo conocido, si Peggy conoce un ciclo hamiltoniano para $G$ , también debe conocer uno para $H.$
Peggy se compromete con $H.$ Podría hacerlo utilizando un esquema de compromiso criptográfico . Alternativamente , podría numerar los vértices de $H.$ Luego, para cada arista de $H$ , en un pequeño trozo de papel, escribe los dos vértices que une la arista. 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 , al mismo tiempo, Victor no tiene 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 problema de isomorfismo gráfico ) , o puede pedirle que muestre un ciclo hamiltoniano en $H.$
Si se le pide a Peggy que demuestre que las dos gráficas son isomorfas, primero descubre todo $H$ (por ejemplo, volteando 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 efectivamente son isomórficos.
Si se le pide a Peggy que demuestre que conoce un ciclo hamiltoniano en $H$ , ella traduce su ciclo hamiltoniano en $G$ a $H$ y solo descubre los bordes del ciclo hamiltoniano. Es decir, Peggy solo voltea exactamente los trozos de papel que corresponden a los bordes del ciclo hamiltoniano, dejando el resto boca abajo. Esto es suficiente para que Víctor compruebe que $H$ efectivamente contiene un ciclo hamiltoniano. $|V(G)|$

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.

Lo completo

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$ ).

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 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.

Solvencia

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.

Variantes del conocimiento cero

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:

Hablamos de conocimiento cero perfecto si las distribuciones producidas por el simulador y el protocolo de prueba se distribuyen exactamente igual. 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 cero computacional si ningún algoritmo eficiente puede distinguir las dos distribuciones.

Tipos de conocimiento cero

Prueba de conocimiento : el conocimiento está oculto en el exponente como en el ejemplo que se muestra arriba.
Criptografía basada en emparejamiento : $dados$ f $(x)$ y $f(y)$ , sin conocer $xey$ , es posible calcular $f($ $x$ $\times$ $y$ $)$ .
Prueba indistinguible de testigos : los verificadores no pueden saber qué testigo se utiliza para producir la prueba.
Cálculo multipartito : si bien cada parte puede guardar su respectivo secreto, juntas producen un resultado.
Firma en anillo : los forasteros no tienen idea de qué clave se utiliza para firmar.

Aplicaciones

Sistemas de autenticación

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]

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. 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 ]}

Desarme nuclear

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]

cadenas de bloques

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]

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 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 un 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 . ^[28]

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. ^[29] 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. ^[30]^[31]

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. ^[32]

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 . ^[33] 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. ^[34]

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]

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 clasificar ampliamente 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 . ^[35] 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.

Ver también

Referencias

^ Aad, Imad (2023), Mulder, Valentín; Mermoud, Alain; Prestamistas, Vicente; Tellenbach, Bernhard (eds.), "Prueba de conocimiento cero", Tendencias en protección de datos y tecnologías de cifrado , Cham: Springer Nature Suiza, págs. 25–30, doi : 10.1007/978-3-031-33386-6_6 , ISBN 978-3-031-33386-6, recuperado el 13 de octubre de 2023
^ Goldreich, Oded (2001). Fundamentos de criptografía Volumen I. Prensa de la Universidad de Cambridge. pag. 184. doi : 10.1017/CBO9780511546891. ISBN 9780511546891.
^ Goldreich, Oded (2001). Fundamentos de criptografía Volumen I. Prensa de la Universidad de Cambridge. pag. 247. doi : 10.1017/CBO9780511546891. ISBN 9780511546891.
^ Goldreich, Oded (2001). Fundamentos de criptografía Volumen I. Prensa de la Universidad de Cambridge. pag. 299. doi : 10.1017/CBO9780511546891. ISBN 9780511546891.
^ ab Blum, Manuel; Feldman, Pablo; Micali, Silvio (1988). "El conocimiento cero no interactivo y sus aplicaciones". Actas del vigésimo simposio anual de ACM sobre teoría de la informática - STOC '88 (PDF) . págs. 103-112. doi :10.1145/62212.62222. ISBN 978-0897912648. S2CID 7282320. Archivado (PDF) desde el original el 14 de diciembre de 2018 . Consultado el 2 de junio de 2022 .{{cite book}}: CS1 maint: date and year (link)
^ ab Wu, Huixin; Wang, Feng (2014). "Un estudio del sistema de prueba de conocimiento cero no interactivo y sus aplicaciones". La Revista del Mundo Científico . 2014 : 560484. doi : 10.1155/2014/560484 . PMC 4032740 . PMID 24883407.
^ Quisquater, Jean-Jacques; Guillou, Luis 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 conferencias sobre 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 utilizar las matemáticas". CordaCon 2017 . Consultado el 13 de septiembre de 2017 .
^ abc Murtagh, Jack (1 de julio de 2023). "¿Dónde está Waldo? Cómo demostrar matemáticamente que lo encontraste sin revelar dónde está". Científico americano . Consultado el 2 de octubre de 2023 .
^ Feige, Uriel; Fiat, Amós; 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 para que nadie más pueda afirmarlo" (PDF) . Actas de la 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 completo problema 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 conferencias sobre 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. S2CID 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 18 de agosto de 2021 .
^ 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 clásico de GMW? El caso de 2PC no interactivo y activamente seguro". Actas de la Conferencia ACM SIGSAC 2020 sobre seguridad informática y de las comunicaciones . CCS '20. Evento virtual, EE.UU.: Asociación de Maquinaria de Computación. págs. 1591-1605. doi :10.1145/3372297.3423366. ISBN 978-1-4503-7089-9. S2CID 226228208.
^ "PPPL y Princeton demuestran una técnica novedosa que puede tener aplicabilidad en futuras conversaciones sobre desarme nuclear - Princeton Plasma Physics Lab". www.pppl.gov . Archivado desde el original el 3 de julio de 2017.
^ a b C Hellwig, Daniel; Karlic, Goran; Huchzermeier, Arnd (3 de mayo de 2020). "Privacidad y anonimato". Construya su propia cadena de bloques . Gestión para profesionales. Enlace Springer. pag. 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 cambio de marca a nuevo nombre y ticker" Firo"". Información privilegiada sobre financiación colectiva. Archivado desde el original el 1 de noviembre de 2020 . Consultado el 4 de noviembre de 2020 .
^ Bonneau, J; Molinero, A; Clark, J; Narayanan, A (2015). "SoK: perspectivas de investigación y desafíos para Bitcoin y las criptomonedas". Simposio IEEE 2015 sobre seguridad y privacidad . San Jose, 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, Alejandro; Garman, Cristina; Verde, Mateo; Miers, Ian; Tromer, Eran; Virza, Madars (18 de mayo de 2014). "Zerocash: pagos anónimos descentralizados de Bitcoin" (PDF) . IEEE . Consultado el 26 de enero de 2016 .
^ Orcutt, Mike. "Un truco criptográfico alucinante promete llevar las cadenas de bloques a la corriente principal". Revisión de tecnología del MIT . Consultado el 18 de diciembre de 2017 .
^ ab Bünz, B; Bootle, D; Boneh, A (2018). "Bulletproofs: pruebas breves para transacciones confidenciales y más". Simposio IEEE 2018 sobre seguridad y privacidad (SP) . San Francisco, California. págs. 315–334. doi : 10.1109/SP.2018.00020 . ISBN 978-1-5386-4353-2. S2CID 3337741.{{cite book}}: CS1 maint: location missing publisher (link)
^ Odendaal, Hansie; Sharrock, Cayle; Heerden, SW. "Bulletproofs y Mimblewimble". Universidad Tari Labs. 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 cero pruebas de conocimiento sin una configuración confiable". Buscador de 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 blockchain a partir de supuestos estándar". Archivo ePrint de criptología (Informe 373) . Consultado el 14 de abril de 2019 .
^ Goldreich, Oded (1985). "Una prueba de conocimiento cero de que un módulo biprimo no es un entero de Blum". Manuscrito inédito .
^ Goldreich, Oded; Micali, Silvio; Wigderson, Avi (1991). "Pruebas que no arrojan 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. CRIPTO 1987: 40-51
^ Ben-Or, Michael; Goldreich, Oded; Goldwasser, Shafi; Hastad, Johan; Kilian, Joe; Micali, Silvio; Rogaway, Phillip (1990). "Todo lo demostrable es demostrable en conocimiento cero". En Goldwasser, S. (ed.). Avances en criptología - CRYPTO '88 . Apuntes de conferencias sobre informática. vol. 403. Springer-Verlag. págs. 37–56.
^ Ben-or, M.; Goldwasser, Shafi; Kilian, J.; Wigderson, A. (1988). "Pruebas interactivas de múltiples probadores: cómo eliminar los supuestos de intratabilidad" (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). "Testigos indistinguibles y protocolos de ocultamiento de testigos". Actas del vigésimo segundo simposio anual de ACM sobre teoría de la informática - STOC '90 . págs. 416–426. CiteSeerX 10.1.1.73.3911 . doi :10.1145/100216.100272. ISBN 978-0897913614. S2CID 11146395.{{cite book}}: CS1 maint: date and year (link)
^ ab Mouris, Dimitris; Tsoutsos, Nektarios Georgios (2021). "Zilch: un marco para implementar pruebas transparentes de conocimiento cero". Transacciones IEEE sobre seguridad y análisis 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 2013 sobre seguridad y privacidad . págs. 238-252. doi :10.1109/SP.2013.47. ISBN 978-0-7695-4977-4. S2CID 1155080.
^ Costello, Craig; Fournet, Cedric; Howell, Jon; Kohlweiss, Markulf; Kreuter, Benjamín; Naehrig, Michael; Parno, Bryan; Zahur, Samee (mayo de 2015). "Geppetto: Computación versátil verificable". Simposio IEEE 2015 sobre seguridad y privacidad . 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. S2CID 3343426.
^ Ben-Sasson, Eli; Chiesa, Alejandro; Genkin, Daniel; Tromer, Eran; Virza, Madars (2013). "SNARKs para C: verificación de ejecuciones de programas de manera sucinta y sin conocimiento". Avances en Criptología – CRYPTO 2013 . Apuntes de conferencias sobre 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). "RAM eficiente y flujo de control en computación subcontratada verificable". Actas del Simposio de 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 fuera de cadena escalables que preservan la privacidad". Conferencia internacional IEEE 2018 sobre Internet de las cosas (IThings) e IEEE Green Computing and Communications (GreenCom) y IEEE Cyber, Physical and Social Computing (CPSCom) e IEEE Smart Data (SmartData) . págs. 1084-1091. doi :10.1109/Cibermática_2018.2018.00199. ISBN 978-1-5386-7975-3. S2CID 49473237.
^ Kosba, Ahmed; Papamanthou, Charalampos; Shi, Elaine (mayo de 2018). "XJsnark: un marco para una computación eficiente y verificable". Simposio IEEE 2018 sobre seguridad y privacidad (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 2018 sobre seguridad y privacidad (SP) . págs. 908–925. doi : 10.1109/SP.2018.00013 . ISBN 978-1-5386-4353-2.
^ Ben-Sasson, Eli; Chiesa, Alejandro; Tromer, Eran; Virza, Madars (20 de agosto de 2014). "Conocimiento cero sucinto no interactivo para una arquitectura 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; Canción, amanecer (2020). "MIRAGE: argumentos sucintos a favor de algoritmos aleatorios con aplicaciones a zk-SNARK universales". Archivo ePrint de criptología .
^ Maller, María; Bowe, Sean; Kohlweiss, Markulf; Meiklejohn, Sarah (6 de noviembre de 2019). "Sonic: SNARK de conocimiento cero a partir de cadenas de referencia estructuradas actualizables y universales de tamaño lineal". Actas de la Conferencia ACM SIGSAC de 2019 sobre seguridad informática y de las comunicaciones. Asociación para Maquinaria de Computación. págs. 2111-2128. doi :10.1145/3319535.3339817. hdl : 20.500.11820/739b94f1-54f0-4ec3-9644-3c95eea1e8f5 . ISBN 9781450367479. S2CID 242772913.
^ Chiesa, Alejandro; Hu, Yuncong; Maller, María; Mishra, Pratyush; Vesely, Noé; Ward, Nicolás (2020). "Marlin: preprocesamiento de zkSNARK con SRS universal y actualizable". Avances en Criptología – EUROCRYPT 2020 . Apuntes de conferencias sobre informática. vol. 12105. Publicación internacional Springer. págs. 738–768. doi :10.1007/978-3-030-45721-1_26. ISBN 978-3-030-45720-4. S2CID 204772154.
^ Gabizon, Ariel; Williamson, Zachary J.; Ciobotaru, Oana (2019). "PLONK: Permutaciones sobre bases de Lagrange para argumentos ecuménicos no interactivos del conocimiento". Archivo ePrint de criptología .
^ Bünz, Benedikt; Fisch, Ben; Szepieniec, Alan (2020). "SNARK transparentes de DARK Compilers". Avances en Criptología – EUROCRYPT 2020 . Apuntes de conferencias sobre informática. vol. 12105. Publicación internacional Springer. págs. 677–706. doi :10.1007/978-3-030-45721-1_24. ISBN 978-3-030-45720-4. S2CID 204892714.
^ Wahby, Riad S.; Tzialla, Ioanna; Shelat, Abhi; Thaler, Justin; Walfish, Michael (mayo de 2018). "ZkSNARK doblemente eficientes sin configuración confiable". Simposio IEEE 2018 sobre seguridad y privacidad (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 prueba recursiva sin una configuración confiable". Archivo ePrint de criptología .
^ Zhang, Jiaheng; Xie, Tiancheng; Zhang, Yupeng; Canción, amanecer (mayo de 2020). "Delegación polinómica transparente y sus aplicaciones a la prueba de conocimiento cero". Simposio IEEE 2020 sobre seguridad y privacidad (SP) . págs. 859–876. doi : 10.1109/SP40000.2020.00052 . ISBN 978-1-7281-3497-0.
^ Ames, Scott; Hazay, Carmit; Ishai, Yuval; Venkisubramaniam, Muthuramakrishnan (30 de octubre de 2017). "Ligero". Actas de la Conferencia ACM SIGSAC 2017 sobre seguridad informática y de las comunicaciones . Asociación para Maquinaria de Computación. págs. 2087-2104. doi :10.1145/3133956.3134104. ISBN 9781450349468. S2CID 5348527.
^ Ben-Sasson, Eli; Chiesa, Alejandro; Riabzev, Michael; Spooner, Nicolás; Virza, Madars; Ward, Nicolás P. (2019). "Aurora: argumentos sucintos y transparentes a favor de R1CS". Avances en Criptología – EUROCRYPT 2019 . Apuntes de conferencias sobre informática. vol. 11476. Publicación internacional Springer. págs. 103-128. doi :10.1007/978-3-030-17653-2_4. ISBN 978-3-030-17652-5. S2CID 52832327.
^ Ben-Sasson, Eli; Bentov, Iddo; Horesh, Yinón; Riabzev, Michael (2019). "Conocimiento cero escalable sin configuración confiable". Avances en Criptología – CRYPTO 2019 . Apuntes de conferencias sobre informática. vol. 11694. Publicación internacional Springer. págs. 701–732. doi :10.1007/978-3-030-26954-8_23. ISBN 978-3-030-26953-1. S2CID 199501907.