Pruebas, argumentos y conocimiento cero

Título original:

Proofs, Arguments, and Zero-Knowledge

Contenido del libro:

Esta monografía trata de la computación verificable (CV). La CV se refiere a protocolos criptográficos denominados pruebas interactivas (PI) y argumentos que permiten a un prover proporcionar una garantía a un verificador de que el prover realizó correctamente un cálculo solicitado. Esta monografía abarca diferentes nociones de pruebas matemáticas y sus aplicaciones en informática y criptografía. Informalmente, lo que entendemos por una prueba es cualquier cosa que convence a alguien de que una afirmación es verdadera, y un "sistema de pruebas" es cualquier procedimiento que decide qué es y qué no es una prueba convincente.

Introducidos en la década de 1980, los PI y los argumentos representaron una importante expansión conceptual de lo que constituye una "prueba" de que una afirmación es verdadera. Tradicionalmente, una prueba es un objeto estático cuya corrección puede comprobarse fácilmente paso a paso. Por el contrario, los PI permiten la interacción entre el probador y el verificador, así como una probabilidad pequeña pero no nula de que una prueba inválida pase la verificación. Los argumentos (pero no los PI) permiten incluso que haya "pruebas" de afirmaciones falsas, siempre y cuando esas "pruebas" requieran un poder computacional exorbitante para encontrarlas. Hasta cierto punto, estas nociones imitan las interacciones en persona que los matemáticos utilizan para convencerse mutuamente de que una afirmación es cierta, sin pasar por el laborioso proceso de escribir y comprobar una prueba estática tradicional.

Célebres resultados teóricos de los años 80 y 90, como IP = PSPACE y MIP = NEXP demostraron que, en principio, afirmaciones sorprendentemente complicadas pueden verificarse de forma eficiente. Además, cualquier argumento puede transformarse en principio en uno de conocimiento cero, lo que significa que las pruebas no revelan más información que su propia validez. Los argumentos de conocimiento-cero tienen innumerables aplicaciones en criptografía.

En la última década, los argumentos de conocimiento-cero de uso general han pasado de la teoría a la práctica. Esto ha abierto nuevas puertas en el diseño de sistemas criptográficos y ha generado nuevas perspectivas sobre el poder de los PI y los argumentos (de conocimiento-cero o de otro tipo). En la actualidad existen no menos de cinco enfoques prometedores para diseñar argumentos de conocimiento-cero eficientes y de uso general. Esta monografía cubre estos enfoques de manera unificada, haciendo hincapié en los puntos en común entre ellos.