stringtranslate.com

Prueba de conocimiento cero no interactiva

Las pruebas de conocimiento cero no interactivas son primitivas criptográficas , en las que el probador puede autenticar la información entre un probador y un verificador, sin revelar ninguna información específica más allá de la validez de la declaración misma. Esto hace innecesaria la comunicación directa entre el probador y el verificador, eliminando efectivamente cualquier intermediario.

La principal ventaja de las pruebas de conocimiento cero no interactivas es que se pueden utilizar en situaciones en las que no hay posibilidad de interacción entre el probador y el verificador, como en transacciones en línea donde las dos partes no pueden comunicarse en tiempo real. Esto hace que las pruebas de conocimiento cero no interactivas sean particularmente útiles en sistemas descentralizados como blockchains , donde las transacciones son verificadas por una red de nodos y no existe una autoridad central que supervise el proceso de verificación. [1]

La mayoría de las pruebas de conocimiento cero no interactivas se basan en construcciones matemáticas como la criptografía de curva elíptica o la criptografía basada en pares , que permiten la creación de pruebas breves y fácilmente verificables de la verdad de una afirmación. A diferencia de las pruebas interactivas de conocimiento cero, que requieren múltiples rondas de interacción entre el probador y el verificador, las pruebas de conocimiento cero no interactivas están diseñadas para ser eficientes y pueden usarse para verificar una gran cantidad de declaraciones simultáneamente. [1]

Historia

Blum , Feldman y Micali [2] demostraron en 1988 que una cadena de referencia común compartida entre el probador y el verificador es suficiente para lograr conocimiento cero computacional sin requerir interacción. Goldreich y Oren [3] dieron resultados de imposibilidad [ se necesita aclaración ] para protocolos de conocimiento cero de una sola vez en el modelo estándar . En 2003, Shafi Goldwasser y Yael Tauman Kalai publicaron un ejemplo de un esquema de identificación para el cual cualquier función hash produciría un esquema de firma digital inseguro. [4]

El modelo influye en las propiedades que se pueden obtener de un protocolo de conocimiento cero. El paso [5] 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 preservan la negación. También se pueden obtener pruebas de conocimiento cero no interactivas en el modelo de oráculo aleatorio utilizando la heurística Fiat-Shamir . [ cita necesaria ]

Aplicaciones de cadena de bloques

Una comparación de los sistemas de prueba más utilizados [ cita necesaria ]

En 2012, Alessandro Chiesa et al desarrollaron el protocolo zk-SNARK, un acrónimo de argumento de conocimiento sucinto no interactivo de conocimiento cero . [6] La primera aplicación generalizada de zk-SNARK fue en el protocolo blockchain Zerocash , donde la criptografía de conocimiento cero proporciona la columna vertebral computacional, al facilitar pruebas matemáticas de que una parte tiene posesión de cierta información sin revelar cuál es esa información. [7] Zcash utilizó zk-SNARK para facilitar cuatro tipos de transacciones distintas: privada, blindaje, desprotección y pública. Este protocolo permitió a los usuarios determinar cuántos datos se compartieron con el libro de contabilidad público para cada transacción. [8] Ethereum zk-Rollups también utiliza zk-SNARK para aumentar la escalabilidad. [9]

En 2017, se lanzó Bulletproofs [10] , 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. [11] Bulletproofs se implementó posteriormente en el protocolo Mimblewimble (la base de Grin and Beam, y Litecoin a través de bloques de extensión) y la criptomoneda Monero . [12]

En 2018, Eli Ben-Sasson, Iddo Bentov, Yinon Horesh y Michael Riabzev introdujeron el protocolo zk-STARK ( argumento de conocimiento transparente escalable de conocimiento cero ) [13] , [14] que ofrece transparencia (sin configuración confiable), tiempo de prueba cuasi lineal y tiempo de verificación polilogarítmica. Los argumentos de conocimiento transparentes, sucintos y de conocimiento cero son un tipo de sistema de prueba criptográfica que permite a una parte (el probador) demostrarle a otra parte (el verificador) que una determinada afirmación es verdadera, sin revelar ninguna información adicional más allá de la verdad de la afirmación. sí mismo. Los zk-STARK son concisos, lo que significa que permiten la creación de pruebas breves que son fáciles de verificar, y son transparentes, lo que significa que cualquiera puede verificar la prueba sin necesidad de información secreta. [14]

A diferencia de la primera generación de zk-SNARK, los zk-STARK, de forma predeterminada, no requieren una configuración confiable, lo que los hace particularmente útiles para aplicaciones descentralizadas como blockchains. Además, los zk-STARK se pueden utilizar para verificar muchas declaraciones a la vez, haciéndolas escalables y eficientes. [1]

En 2019, se presentaron zk-SNARK recursivos HALO sin una configuración confiable. [15] Pickles [16] zk-SNARK, basados ​​en la construcción anterior, impulsan a Mina, la primera cadena de bloques sucintamente verificable. [17]

A continuación se proporciona una lista de bibliotecas y protocolos a prueba de conocimiento cero junto con comparaciones basadas en la transparencia, la universalidad y la seguridad poscuántica plausible. 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.

Definición

Originalmente, [2] 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. Puede, por ejemplo, consistir en elementos de grupo elegidos al azar que utilicen todas las partes del protocolo. Aunque los elementos del grupo son aleatorios, la cadena de referencia no lo es, ya que contiene una determinada estructura (por ejemplo, elementos del grupo) que se distingue de la aleatoriedad. Posteriormente, Feige, Lapidot y Shamir [37] introdujeron las pruebas de conocimiento cero con múltiples teoremas como una noción más versátil para las pruebas de conocimiento cero no interactivas.

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 potentes y eficientes. La idea fundamental fue ocultar los valores para la evaluación del emparejamiento en un compromiso . Utilizando diferentes esquemas de compromiso, esta idea se utilizó para construir sistemas de prueba de conocimiento cero bajo el ocultamiento de subgrupos [38] y bajo el supuesto lineal decisional . [39] Estos sistemas de prueba demuestran la satisfacibilidad del circuito y, por lo tanto, según el teorema de Cook-Levin, permiten demostrar la pertenencia a cada idioma en 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.

Se han propuesto sistemas de prueba bajo el ocultamiento de subgrupos , el supuesto lineal decisional y el supuesto externo de Diffie-Hellman que permiten probar directamente las ecuaciones de productos de emparejamiento que son comunes en la criptografía basada en emparejamiento . [40]

Bajo supuestos de conocimiento sólidos, se sabe cómo crear sistemas de prueba computacionalmente sólidos de longitud sublineal para lenguajes NP completos . Más precisamente, la prueba en tales sistemas de prueba consta sólo de un pequeño número de elementos de grupo bilineal. [41] [42]

Referencias

  1. ^ abcGong , Yinjie; Jin, Yifei; Li, Yu-chan; Liu, Ziyi; Zhu, Zhiyi (enero de 2022). "Análisis y comparación del principal esquema de prueba de conocimiento cero". 2022 Conferencia Internacional sobre Big Data, Información y Redes Informáticas (BDICN) . págs. 366–372. doi :10.1109/BDICN55575.2022.00074. ISBN 978-1-6654-8476-3. S2CID  248267862.
  2. ^ ab Manuel Blum, Paul Feldman y Silvio Micali. Conocimiento cero no interactivo y sus aplicaciones. Actas del vigésimo simposio anual de ACM sobre teoría de la informática (STOC 1988). 103–112. 1988
  3. ^ Oded Goldreich y Yair Oren. Definiciones y propiedades de los sistemas de prueba de conocimiento cero. Revista de criptología. Volumen 7 (1). 1–32. 1994 (PS)
  4. ^ Shafi Goldwasser y Yael Kalai. Sobre la (in)seguridad del paradigma Fiat-Shamir. Actas del 44º Simposio anual del IEEE sobre fundamentos de la informática (FOCS'03). 2003
  5. ^ Paso Rafael. Sobre la negación en la cadena de referencia común y el modelo aleatorio de Oracle. Avances en criptología - CRYPTO 2003. 316–337. 2003 (PS)
  6. ^ Bitansky, Nir; Canetti, corrió; Chiesa, Alejandro; Tromer, Eran (enero de 2012). "Desde la resistencia a la colisión extraíble hasta argumentos de conocimiento sucintos y no interactivos, y viceversa". Actas de la 3.ª Conferencia sobre Innovaciones en Informática Teórica sobre -ITCS '12 . ACM . págs. 326–349. doi :10.1145/2090236.2090263. ISBN 978-1-4503-1115-1. S2CID  2576177.
  7. ^ 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 .
  8. ^ Ben-Sasson, Eli; Chiesa, Alejandro. "¿Qué son los zk-SNARK?". z.efectivo . Consultado el 3 de noviembre de 2022 .
  9. ^ "Acumulaciones de conocimiento cero". ethereum.org . Consultado el 25 de febrero de 2023 .
  10. ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrés; Wuille, Pieter; Maxwell, Greg (mayo de 2018). "Balas: pruebas breves para transacciones confidenciales y más". Simposio IEEE 2018 sobre seguridad y privacidad (SP) . págs. 315–334. doi :10.1109/SP.2018.00020. ISBN 978-1-5386-4353-2. S2CID  3337741.
  11. ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrés; Wuille, Pieter; Maxwell, Greg (mayo de 2018). "Balas: pruebas breves para transacciones confidenciales y más" (PDF) . Simposio IEEE 2018 sobre seguridad y privacidad (SP) . págs. 315–334. doi :10.1109/SP.2018.00020. ISBN 978-1-5386-4353-2. S2CID  3337741 . Consultado el 2 de diciembre de 2022 .
  12. ^ 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 .
  13. ^ http://www.cs.technion.ac.il/RESEARCH_DAY_17/POSTERS/michael_riabzev.pdf
  14. ^ a b C Eli Ben-Sasson; Iddo Bentov; Yinón Horesh; Michael Riabzev (6 de marzo de 2018). "Integridad computacional segura, escalable, transparente y poscuántica" (PDF) . Asociación Internacional para la Investigación Criptológica . Consultado el 24 de octubre de 2021 .
  15. ^ ab Bowe, Sean; Grigg, Jack; Hopwood, Daira (2019). "Composición de prueba recursiva sin una configuración confiable". Archivo ePrint de criptología .
  16. ^ "Conozca a Pickles SNARK: Habilitación de contratos inteligentes en el protocolo Coda". Protocolo Mina . Consultado el 25 de febrero de 2023 .
  17. ^ Bonneau, José; Meckler, Izaak; Rao, V.; Evan; Shapiro (2021). "Mina: criptomoneda descentralizada a escala". S2CID  226280610. {{cite web}}: Falta o está vacío |url=( ayuda )
  18. ^ Parno, Bryan; Howell, Jon; Gentry, Craig; Raykova, Mariana (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.
  19. ^ Costello, Craig; Fournet, Cédric; 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. ISBN 978-1-4673-6949-7. S2CID  3343426.
  20. ^ 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". En Canetti, Ran; Garay, Juan A. (eds.). Avances en Criptología – CRYPTO 2013 . Apuntes de conferencias sobre informática. vol. 8043. Berlín, Heidelberg: Springer. págs. 90-108. doi :10.1007/978-3-642-40084-1_6. ISBN 978-3-642-40084-1.
  21. ^ Wahby, Riad S.; Setty, Srinath; Ren, Zuocheng; Blumberg, Andrew J.; Walfish, Michael (2015). RAM eficiente y flujo de control en computación subcontratada verificable. doi :10.14722/ndss.2015.23097. ISBN 978-1-891562-38-9. Consultado el 25 de febrero de 2023 . {{cite book}}: |website=ignorado ( ayuda )
  22. ^ 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. S2CID  41548742.
  23. ^ Ben-Sasson, Eli; Chiesa, Alejandro; Tromer, Eran; Virza, Madars (2014). Conocimiento cero sucinto {no interactivo} para una arquitectura von Neumann. págs. 781–796. ISBN 978-1-931971-15-7.
  24. ^ 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 .
  25. ^ Maller, María; Bowe, Sean; Kohlweiss, Markulf; Meiklejohn, Sarah (6 de noviembre de 2019). "Sonic". Actas de la Conferencia ACM SIGSAC de 2019 sobre seguridad informática y de las comunicaciones. CCS '19. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 2111-2128. doi :10.1145/3319535.3339817. ISBN 978-1-4503-6747-9. S2CID  60442921.
  26. ^ Chiesa, Alejandro; Hu, Yuncong; Maller, María; Mishra, Pratyush; Vesely, Noé; Ward, Nicolás (2020). "Marlin: preprocesamiento de zkSNARK con SRS universal y actualizable". En Canteaut, Ana; Ishai, Yuval (eds.). Avances en Criptología – EUROCRYPT 2020 . Apuntes de conferencias sobre informática. vol. 12105. Cham: Editorial Internacional Springer. págs. 738–768. doi :10.1007/978-3-030-45721-1_26. ISBN 978-3-030-45721-1. S2CID  204772154.
  27. ^ 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 .
  28. ^ Bünz, Benedikt; Fisch, Ben; Szepieniec, Alan (2020). "SNARK transparentes de DARK Compilers". En Canteaut, Ana; Ishai, Yuval (eds.). Avances en Criptología – EUROCRYPT 2020 . Apuntes de conferencias sobre informática. vol. 12105. Cham: Editorial Internacional Springer. págs. 677–706. doi :10.1007/978-3-030-45721-1_24. ISBN 978-3-030-45721-1. S2CID  204892714.
  29. ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrés; Wuille, Pieter; Maxwell, Greg (mayo de 2018). "Balas: pruebas breves para transacciones confidenciales y más". Simposio IEEE 2018 sobre seguridad y privacidad (SP) . págs. 315–334. doi :10.1109/SP.2018.00020. ISBN 978-1-5386-4353-2. S2CID  3337741.
  30. ^ 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. S2CID  549873.
  31. ^ 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. S2CID  209467198.
  32. ^ Ames, Scott; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 de octubre de 2017). "Lígero". Actas de la Conferencia ACM SIGSAC 2017 sobre seguridad informática y de las comunicaciones . CCS '17. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 2087-2104. doi :10.1145/3133956.3134104. ISBN 978-1-4503-4946-8. S2CID  5348527.
  33. ^ 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". En Ishai, Yuval; Rijmen, Vicente (eds.). Avances en Criptología – EUROCRYPT 2019 . Apuntes de conferencias sobre informática. vol. 11476. Cham: Springer International Publishing. págs. 103-128. doi :10.1007/978-3-030-17653-2_4. ISBN 978-3-030-17653-2. S2CID  52832327.
  34. ^ Ben-Sasson, Eli; Bentov, Iddo; Horesh, Yinón; Riabzev, Michael (2019). "Conocimiento cero escalable sin configuración confiable". En Boldyreva, Alexandra; Micciancio, Daniele (eds.). Avances en Criptología – CRYPTO 2019 . Apuntes de conferencias sobre informática. vol. 11694. Cham: Springer International Publishing. págs. 701–732. doi :10.1007/978-3-030-26954-8_23. ISBN 978-3-030-26954-8. S2CID  199501907.
  35. ^ Computación, confiable (30 de agosto de 2021). "Pruebas transparentes de conocimiento cero sin nada". Medio . Consultado el 25 de febrero de 2023 .
  36. ^ 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.
  37. ^ Uriel Feige, Dror Lapidot, Adi Shamir: múltiples pruebas de conocimiento cero no interactivas bajo supuestos generales. SIAM J. Computación. 29(1): 1–28 (1999)
  38. ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: Conocimiento cero perfecto no interactivo para NP. EUROCRIPTA 2006: 339–358
  39. ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: Zaps no interactivos y nuevas técnicas para NIZK. CRIPTO 2006: 97–111
  40. ^ Jens Groth, Amit Sahai: Sistemas de prueba eficientes no interactivos para grupos bilineales. EUROCRIPTA 2008: 415–432
  41. ^ Jens Groth. Argumentos breves de conocimiento cero no interactivos basados ​​en emparejamientos. ASIACRIPT 2010: 321–340
  42. ^ Helger Lipmaa. Conjuntos libres de progresión y argumentos de conocimiento cero no interactivos basados ​​en emparejamientos sublineales. TCC 2012: 169–189