Las pruebas de conocimiento cero no interactivas , también conocidas como NIZK, [1] zk-SNARK, [2] zk-STARK [3], son pruebas de conocimiento cero que no requieren interacción [se necesita aclaración ] entre el probador y el verificador.
Historia
Blum , Feldman y Micali [4] demostraron en 1988 que una cadena de referencia común compartida entre el probador y el verificador es suficiente para lograr un conocimiento cero computacional sin requerir interacción. Goldreich y Oren [5] dieron resultados imposibles [ aclaración necesaria ] para protocolos de conocimiento cero de una sola vez en el modelo estándar . En 2003, Shafi Goldwasser y Yael Tauman Kalai publicaron una instancia de un esquema de identificación para el cual cualquier función hash produciría un esquema de firma digital inseguro. [6] Estos resultados no son contradictorios, ya que el resultado de imposibilidad [ aclaración necesaria ] de Goldreich y Oren no se sostiene en el modelo de cadena de referencia común o en el modelo de oráculo aleatorio . Sin embargo, las pruebas de conocimiento cero no interactivas muestran una separación entre las tareas criptográficas que se pueden lograr en el modelo estándar y las que se pueden lograr en modelos extendidos "más potentes". [ cita requerida ]
El modelo influye en las propiedades que se pueden obtener de un protocolo de conocimiento cero. Pass [7] mostró que en el modelo de cadena de referencia común, los protocolos de conocimiento cero no interactivos no conservan todas las propiedades de los protocolos de conocimiento cero interactivos; por ejemplo, no conservan la negación.
Las pruebas no interactivas de conocimiento cero también se pueden obtener en el modelo de oráculo aleatorio utilizando la heurística Fiat-Shamir . Un artículo de 2012 de Bitansky et al introdujo el acrónimo zk-SNARK para un argumento de conocimiento sucinto y no interactivo de conocimiento cero . [2] La primera aplicación generalizada de zk-SNARKs fue en el protocolo de cadena de bloques Zerocash , donde la criptografía de conocimiento cero proporciona la columna vertebral computacional, facilitando pruebas matemáticas de que una parte tiene posesión de cierta información sin revelar cuál es esa información. [8] [9] Para el 2021, "82 criptomonedas por un valor total de US $ 8.850 millones [cifraron] sus transacciones con pruebas de conocimiento cero o tecnología privada similar". [8]
En 2017, se lanzó Bulletproofs , que permite demostrar que un valor comprometido está en un rango utilizando un número logarítmico (en la longitud de bits del rango) de elementos de campo y grupo. [10] Bulletproofs se implementó más tarde en el protocolo Mimblewimble (donde se basan las criptomonedas Grin y Beam) y la criptomoneda Monero . [11]
En 2018, la zk- STARK (argumento transparente de conocimiento cero escalable de Conocimiento) [12] se introdujo protocolo, [13] ofrenda transparencia (configuración no de confianza), el tiempo proving cuasi-lineal, y el tiempo de verificación de poli-logarítmica. [3]
Definición
Originalmente, [4] el conocimiento cero no interactivo solo se definió como un único sistema de prueba de teoremas. En tal sistema, cada prueba requiere su propia cadena de referencia común nueva. Una cadena de referencia común en general no es una cadena aleatoria. Por ejemplo, puede consistir en elementos de grupo elegidos al azar que utilizan todas las partes del protocolo. Aunque los elementos del grupo son aleatorios, la cadena de referencia no lo es porque contiene una determinada estructura (por ejemplo, elementos del grupo) que se distingue de la aleatoriedad. Posteriormente, Feige, Lapidot y Shamir [14] introdujeron las pruebas de conocimiento cero de múltiples teoremas como una noción más versátil para las pruebas de conocimiento cero no interactivas.
En este modelo, el probador y el verificador están en posesión de una cadena de referencia muestreada de una distribución, D , por una configuración confiable. Para probar declaracióncon testigo w , el probador corre y envía la prueba, , al verificador. El verificador acepta siy rechaza lo contrario. Para tener en cuenta el hecho de que puede influir en las declaraciones que se están probando, la relación de testigos se puede generalizar a parametrizado por . [ cita requerida ]
Lo completo
La verificación tiene éxito para todos y cada . [ cita requerida ]
Más formalmente, [ cita requerida ]
para todos k , todos, y todo :
Solvencia
La solidez requiere que ningún probador pueda hacer que el verificador acepte una declaración incorrecta excepto con alguna pequeña probabilidad. El límite superior de esta probabilidad se denomina error de solidez de un sistema de prueba. [ cita requerida ]
Más formalmente, [ cita requerida ]
por cada probador malicioso, , existe una función insignificante ,, tal que
La definición anterior requiere que el error de solidez sea insignificante en el parámetro de seguridad, k . Al aumentar k, el error de solidez puede reducirse arbitrariamente. Si el error de solidez es 0 para todo k , hablamos de solidez perfecta .
Conocimiento cero de múltiples teoremas
Un sistema de prueba no interactivo es conocimiento cero de múltiples teoremas, si existe un simulador, , de modo que para todos los adversarios de tiempo polinomial no uniforme, , [ cita requerida ]
Aquí salidas por y ambos oráculos salida fracaso de otra manera. [ cita requerida ]
Pruebas no interactivas basadas en emparejamiento
La criptografía basada en emparejamiento ha dado lugar a varios avances criptográficos. Uno de estos avances son las pruebas de conocimiento cero no interactivas más poderosas y eficientes. La idea fundamental fue esconder los valores para la evaluación del binomio en un compromiso . Usando diferentes esquemas de compromiso, esta idea se utilizó para construir sistemas de prueba de conocimiento cero bajo el subgrupo ocultación [15] y bajo el supuesto lineal decisional . [1] Estos sistemas de prueba prueban la satisfacibilidad del circuito y, por lo tanto, según el teorema de Cook-Levin, permiten probar la pertenencia a todos los idiomas de NP. El tamaño de la cadena de referencia común y las pruebas es relativamente pequeño; sin embargo, transformar una declaración en un circuito booleano supone una sobrecarga considerable.
Sistemas de prueba con arreglo al escondite sub-grupo , suposición lineal decisional , y supuesto de Diffie-Hellman externa que permitan probar directamente las ecuaciones de productos de emparejamiento que son comunes en la criptografía basado en el emparejamiento se han propuesto. [dieciséis]
Bajo fuertes supuestos de conocimiento , se sabe cómo crear sistemas computacionalmente sólidos a prueba de longitud sublineal para lenguajes NP-completos . Más precisamente, la prueba en tales sistemas de prueba consta solo de un pequeño número de elementos de grupo bilineal . [17] [18]
Referencias
- ^ a b Jens Groth, Rafail Ostrovsky, Amit Sahai: Zaps no interactivos y nuevas técnicas para NIZK. CRYPTO 2006: 97–111
- ^ a b Bitansky, Nir; Canetti, Ran; Chiesa, Alessandro; Tromer, Eran (enero de 2012). "Desde la resistencia a colisiones extraíble hasta los argumentos de conocimiento sucintos y no interactivos, y viceversa" . Actas de la 3ª Conferencia sobre Innovaciones en Informática Teórica en - ITCS '12 . ACM . págs. 326–349. doi : 10.1145 / 2090236.2090263 . ISBN 9781450311151. S2CID 2576177 .
- ^ a b https://eprint.iacr.org/2018/046.pdf
- ↑ a b Manuel Blum, Paul Feldman y Silvio Micali. El conocimiento cero no interactivo y sus aplicaciones. Actas del vigésimo simposio anual de ACM sobre teoría de la computación (STOC 1988). 103–112. 1988
- ^ Oded Goldreich y Yair Oren. Definiciones y propiedades de los sistemas de prueba de conocimiento cero. Revista de criptología. Vol. 7 (1). 1-32. 1994 (PS)
- ^ Shafi Goldwasser y Yael Kalai. Sobre la (In) seguridad del Paradigma Fiat-Shamir. Actas del 44º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación (FOCS'03). 2003
- ^ Paso de Rafael. Sobre la denegación en la cadena de referencia común y el modelo aleatorio de Oracle. Avances en criptología - CRYPTO 2003. 316–337. 2003 (PS)
- ^ a b Bambysheva, Nina (13 de febrero de 2021). "Satoshi & Company: los 10 libros blancos científicos más importantes en el desarrollo de criptomonedas" . Forbes . Consultado el 13 de febrero de 2021 .
- ^ 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 de Bitcoin" (PDF) . IEEE . Consultado el 26 de enero de 2016 .
- ^ http://web.stanford.edu/~buenz/pubs/bulletproofs.pdf
- ^ 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 .
- ^ http://www.cs.technion.ac.il/RESEARCH_DAY_17/POSTERS/michael_riabzev.pdf
- ^ Integridad computacional segura escalable, transparente y post-cuántica, Ben-Sasson, Eli y Bentov, Iddo y Horesh, Yinon y Riabzev, Michael, 2018
- ^ Uriel Feige, Dror Lapidot, Adi Shamir: múltiples pruebas de conocimiento cero no interactivas bajo supuestos generales. SIAM J. Comput. 29 (1): 1 a 28 (1999)
- ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: conocimiento cero perfecto no interactivo para NP. EUROCRYPT 2006: 339–358
- ^ Jens Groth, Amit Sahai: sistemas de prueba eficientes no interactivos para grupos bilineales. EUROCRYPT 2008: 415–432
- ^ Jens Groth. Argumentos breves de conocimiento cero, no interactivos, basados en emparejamientos. ASIACRYPT 2010: 321–340
- ^ Helger Lipmaa. Conjuntos sin progresión y argumentos de conocimiento cero no interactivos basados en emparejamientos sublineales. TCC 2012: 169–189
enlaces externos
- Un sistema de prueba de conocimiento cero estadístico no interactivo eficiente para productos prime cuasi seguros