stringtranslate.com

Prueba de conocimiento cero no interactiva

Las pruebas de conocimiento cero no interactivas son primitivas criptográficas , en las que la información entre un probador y un verificador puede ser autenticada por el probador, sin revelar ninguna información específica más allá de la validez de la declaración en sí. 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 existe posibilidad de interacción entre el probador y el verificador, como en las transacciones en línea en las que 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 las cadenas de bloques , donde las transacciones son verificadas por una red de nodos y no hay 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 emparejamiento , que permiten la creación de pruebas breves y fácilmente verificables de la verdad de una afirmación. A diferencia de las pruebas de conocimiento cero interactivas, que requieren múltiples rondas de interacción entre el demostrador 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 afirmaciones 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 [ aclaración necesaria ] para protocolos de conocimiento cero de un solo uso 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á un esquema de firma digital inseguro. [4]

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

Aplicaciones de blockchain

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

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-SNARKs fue en el protocolo de cadena de bloques 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-SNARKs para facilitar cuatro tipos de transacciones distintas: privada, blindada, desblindada y pública. Este protocolo permitió a los usuarios determinar cuántos datos se compartían con el libro mayor público para cada transacción. [8] Los zk-Rollups de Ethereum también utilizan zk-SNARKs para aumentar la escalabilidad. [9]

En 2017, se lanzó Bulletproofs [10] , que permite demostrar que un valor confirmado 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ó más tarde en el protocolo Mimblewimble (la base de Grin y 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 y escalable de conocimiento cero ) [13] , [14] que ofrece transparencia (sin configuración confiable), tiempo de prueba cuasi lineal y tiempo de verificación polilogarítmico. Los argumentos de conocimiento transparentes y sucintos de conocimiento cero son un tipo de sistema de prueba criptográfica que permite a una parte (el demostrador) demostrar a otra parte (el verificador) que una determinada declaración es verdadera, sin revelar ninguna información adicional más allá de la verdad de la declaración misma. Los zk-STARK son sucintos, lo que significa que permiten la creación de pruebas cortas que son fáciles de verificar, y son transparentes, lo que significa que cualquiera puede verificar la prueba sin necesidad de ninguna información secreta. [14]

A diferencia de la primera generación de zk-SNARK, los zk-STARK, por defecto, no requieren una configuración confiable, lo que los hace particularmente útiles para aplicaciones descentralizadas como las cadenas de bloques. Además, los zk-STARK se pueden usar para verificar muchas declaraciones a la vez, lo que los hace escalables y eficientes. [1]

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

A continuación se ofrece una lista de protocolos y bibliotecas de 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 poscuántico plausible es aquel que no es susceptible a ataques conocidos que involucran algoritmos cuánticos.

Definición

Originalmente, [2] el conocimiento cero no interactivo se definió únicamente como un sistema de prueba de un solo teorema. En un sistema de este tipo, 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 aleatoriamente que todas las partes del protocolo utilizan. Aunque los elementos del grupo son aleatorios, la cadena de referencia no lo es, ya que contiene una cierta estructura (por ejemplo, elementos del grupo) que se distingue de la aleatoriedad. Posteriormente, Feige, Lapidot y Shamir [37] introdujeron pruebas de conocimiento cero de 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 seminal fue ocultar los valores para la evaluación de emparejamiento en un compromiso . Utilizando diferentes esquemas de compromiso, esta idea se utilizó para construir sistemas de prueba de conocimiento cero bajo la ocultación de subgrupos [38] y bajo el supuesto lineal de decisión . [39] Estos sistemas de prueba prueban la satisfacibilidad del circuito y, por lo tanto, mediante el teorema de Cook-Levin, permiten probar la pertenencia para cada lenguaje 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 implica una sobrecarga considerable.

Se han propuesto sistemas de prueba bajo la ocultación de subgrupos , el supuesto lineal decisional y el supuesto externo de Diffie-Hellman que permiten probar directamente las ecuaciones de producto 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 consiste solo en un pequeño número de elementos de grupo bilineales. [41] [42]

Referencias

  1. ^ abc Gong, Yinjie; Jin, Yifei; Li, Yuchan; Liu, Ziyi; Zhu, Zhiyi (enero de 2022). "Análisis y comparación del principal esquema de prueba de conocimiento cero". Conferencia internacional de 2022 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. Número de identificación del sujeto  248267862.
  2. ^ de Manuel Blum, Paul Feldman y Silvio Micali. Conocimiento cero no interactivo y sus aplicaciones. Actas del vigésimo simposio anual de la ACM sobre teoría de la computación (STOC 1988). 103–112. 1988
  3. ^ Oded Goldreich y Yair Oren. Definiciones y propiedades de los sistemas de prueba de conocimiento cero. Journal of Cryptology. Vol 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. ^ Rafael Pass. Sobre la negabilidad en la cadena de referencia común y el modelo de oráculo aleatorio. Avances en criptología – CRYPTO 2003. 316–337. 2003 (PS)
  6. ^ Bitansky, Nir; Canetti, Ran; Chiesa, Alessandro; Tromer, Eran (enero de 2012). "De la resistencia a colisiones extraíble a 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. Número de identificación del sujeto  2576177.
  7. ^ 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 .
  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, Andrew; Wuille, Pieter; Maxwell, Greg (mayo de 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) . págs. 315–334. doi :10.1109/SP.2018.00020. ISBN . 978-1-5386-4353-2. Número de identificación del sujeto  3337741.
  11. ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (mayo de 2018). "Bulletproofs: Short Proofs for Confidential Transactions and More" (PDF) . Simposio IEEE sobre seguridad y privacidad de 2018 (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 and Mimblewimble". Tari Labs University. 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. ^ abc Eli Ben-Sasson; Iddo Bentov; Yinon Horesh; Michael Riabzev (6 de marzo de 2018). "Integridad computacional segura, escalable, transparente y postcuántica" (PDF) . Asociación Internacional de 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 de ePrints de criptología .
  16. ^ "Conoce a Pickles SNARK: Habilitación de contratos inteligentes en el protocolo Coda". Protocolo Mina . Consultado el 25 de febrero de 2023 .
  17. ^ Bonneau, Joseph; Meckler, Izaak; Rao, V.; Evan; Shapiro (2021). "Mina: criptomoneda descentralizada a escala" (PDF) . S2CID  226280610.
  18. ^ Parno, Bryan; Howell, Jon; Gentry, Craig; Raykova, Mariana (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  .​
  19. ^ Costello, Craig; Fournet, Cédric; 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. ISBN 978-1-4673-6949-7. Número de identificación del sujeto  3343426.
  20. ^ 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". En Canetti, Ran; Garay, Juan A. (eds.). Avances en criptología – CRYPTO 2013. Apuntes de clase en 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 .
  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 sobre seguridad y privacidad de 2018 (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; Song, Dawn (2020). "MIRAGE: argumentos sucintos a favor de algoritmos aleatorios con aplicaciones a zk-SNARKs universales". Archivo de ePrints de criptología .
  25. ^ Maller, Mary; 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.: Association for Computing Machinery. págs. 2111–2128. doi :10.1145/3319535.3339817. ISBN 978-1-4503-6747-9.S2CID60442921  .​
  26. ^ Chiesa, Alessandro; Hu, Yuncong; Maller, Mary; Mishra, Pratyush; Vesely, Noah; Ward, Nicholas (2020). "Marlin: preprocesamiento de zkSNARK con SRS universal y actualizable". En Canteaut, Anne; Ishai, Yuval (eds.). Avances en criptología – EUROCRYPT 2020 . Apuntes de clase en informática. Vol. 12105. Cham: Springer International Publishing. págs. 738–768. doi :10.1007/978-3-030-45721-1_26. ISBN 978-3-030-45721-1. Número de identificación del sujeto  204772154.
  27. ^ 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 .
  28. ^ Bünz, Benedikt; Fisch, Ben; Szepieniec, Alan (2020). "SNARK transparentes de compiladores DARK". En Canteaut, Anne; Ishai, Yuval (eds.). Avances en criptología – EUROCRYPT 2020 . Apuntes de clase en informática. Vol. 12105. Cham: Springer International Publishing. págs. 677–706. doi :10.1007/978-3-030-45721-1_24. ISBN 978-3-030-45721-1. Número de identificación del sujeto  204892714.
  29. ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (mayo de 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) . págs. 315–334. doi :10.1109/SP.2018.00020. ISBN . 978-1-5386-4353-2. Número de identificación del sujeto  3337741.
  30. ^ 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.S2CID 549873  .
  31. ^ 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.S2CID209467198  .​
  32. ^ 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 . CCS '17. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 2087–2104. doi :10.1145/3133956.3134104. ISBN 978-1-4503-4946-8.S2CID5348527  .​
  33. ^ Ben-Sasson, Eli; Chiesa, Alessandro; Riabzev, Michael; Spooner, Nicholas; Virza, Madars; Ward, Nicholas P. (2019). "Aurora: argumentos sucintos y transparentes a favor de R1CS". En Ishai, Yuval; Rijmen, Vincent (eds.). Avances en criptología – EUROCRYPT 2019. Apuntes de clase en 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. Número de identificación del sujeto  52832327.
  34. ^ Ben-Sasson, Eli; Bentov, Iddo; Horesh, Yinon; Riabzev, Michael (2019). "Conocimiento cero escalable sin configuración de confianza". En Boldyreva, Alexandra; Micciancio, Daniele (eds.). Avances en criptología – CRYPTO 2019. Apuntes de clase en 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. ^ Computing, Trustworthy (30 de agosto de 2021). "Pruebas transparentes de conocimiento cero con cero". Medium . 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 forense 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 no interactivas de conocimiento cero bajo supuestos generales. SIAM J. Comput. 29(1): 1–28 (1999)
  38. ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: Conocimiento cero perfecto y no interactivo para NP. EUROCRYPT 2006: 339–358
  39. ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: Zaps no interactivos y nuevas técnicas para NIZK. CRYPTO 2006: 97–111
  40. ^ Jens Groth, Amit Sahai: Sistemas de prueba no interactivos eficientes para grupos bilineales. EUROCRYPT 2008: 415–432
  41. ^ Jens Groth. Argumentos breves de conocimiento cero no interactivos basados ​​en emparejamientos. ASIACRYPT 2010: 321–340
  42. ^ Helger Lipmaa. Conjuntos sin progresión y argumentos de conocimiento cero no interactivos basados ​​en emparejamiento sublineal. TCC 2012: 169–189