Prueba de conocimiento

En criptografía , una prueba de conocimiento es una prueba interactiva en la que el probador logra "convencer" a un verificador de que el probador sabe algo. Lo que significa que una máquina "sepa algo" se define en términos de computación. Una máquina "sabe algo", si este algo puede ser calculado, dada la máquina como entrada. Como el programa del probador no necesariamente escupe el conocimiento en sí (como es el caso de las pruebas de conocimiento cero ^[1] ), se introduce una máquina con un programa diferente, llamado extractor de conocimiento, para capturar esta idea. Estamos principalmente interesados ​​en lo que se puede probar mediante máquinas polinómicas limitadas en el tiempo. En este caso, el conjunto de elementos de conocimiento está limitado a un conjunto de testigos de algún lenguaje en NP .

Sea un enunciado de lenguaje en NP, y el conjunto de testigos para x que deben aceptarse en la prueba. Esto nos permite definir la siguiente relación: . ${\estilo de visualización x}$${\estilo de visualización L}$${\estilo de visualización W(x)}$${\displaystyle R=\{(x,w):x\en L,w\en W(x)\}}$

Una prueba de conocimiento para la relación con el error de conocimiento es un protocolo de dos partes con un demostrador y un verificador con las dos propiedades siguientes: ${\estilo de visualización R}$${\estilo de visualización \kappa}$${\estilo de visualización P}$${\estilo de visualización V}$

1. Completitud : Si , entonces el probador que conoce al testigo logra convencer al verificador de su conocimiento. Más formalmente: , es decir, dada la interacción entre el probador P y el verificador V, la probabilidad de que el verificador esté convencido es 1.${\displaystyle (x,w)\en R}$${\estilo de visualización P}$${\estilo de visualización w}$${\estilo de visualización x}$${\estilo de visualización V}$${\displaystyle \Pr(P(x,w)\leftrightarrow V(x)\rightarrow 1)=1}$
2. Validez : La validez requiere que la probabilidad de éxito de un extractor de conocimiento al extraer el testigo, dado el acceso del oráculo a un probador posiblemente malicioso , sea al menos tan alta como la probabilidad de éxito del probador al convencer al verificador. Esta propiedad garantiza que ningún probador que no conozca al testigo pueda tener éxito en convencer al verificador.${\estilo de visualización E}$${\displaystyle {\tilde {P}}}$${\displaystyle {\tilde {P}}}$

Esta es una definición más rigurosa de Validez : ^[2]

Sea una relación de testigos, el conjunto de todos los testigos para el valor público y el error de conocimiento. Una prueba de conocimiento es válida si existe una máquina de tiempo polinomial , dado el acceso de oráculo a , tal que para cada , es el caso de que y${\estilo de visualización R}$${\estilo de visualización W(x)}$${\estilo de visualización x}$${\estilo de visualización \kappa}$${\estilo de visualización \kappa}$${\estilo de visualización E}$${\displaystyle {\tilde {P}}}$${\displaystyle {\tilde {P}}}$${\displaystyle E^{{\tilde {P}}(x)}(x)\en W(x)\cup \{\bot \}}$${\displaystyle \Pr(E^{{\tilde {P}}(x)}(x)\in W(x))\geq \Pr({\tilde {P}}(x)\leftrightarrow V(x)\rightarrow 1)-\kappa (x).}$

El resultado significa que la máquina de Turing no llegó a una conclusión. ${\estilo de visualización \bot}$${\estilo de visualización E}$

El error de conocimiento denota la probabilidad de que el verificador acepte , aunque el probador en realidad no conozca a un testigo . El extractor de conocimiento se utiliza para expresar lo que se entiende por el conocimiento de una máquina de Turing . Si puede extraer de , decimos que conoce el valor de . ${\displaystyle \kappa(x)}$${\estilo de visualización V}$${\estilo de visualización x}$${\estilo de visualización w}$${\estilo de visualización E}$${\estilo de visualización E}$${\estilo de visualización w}$${\displaystyle {\tilde {P}}}$${\displaystyle {\tilde {P}}}$${\estilo de visualización w}$

Esta definición de la propiedad de validez es una combinación de las propiedades de validez y validez fuerte. ^[2] Para pequeños errores de conocimiento , como por ejemplo o , puede verse como más fuerte que la solidez de las pruebas interactivas ordinarias . ${\displaystyle \kappa(x)}$${\estilo de visualización 2^{-80}}$${\displaystyle 1/\mathrm {poli} (|x|)}$

Para definir una prueba de conocimiento específica, no solo es necesario definir el lenguaje, sino también los testigos que el verificador debe conocer. En algunos casos, demostrar la pertenencia a un lenguaje puede ser fácil, mientras que calcular un testigo específico puede ser difícil. Esto se explica mejor con un ejemplo:

Sea un grupo cíclico con generador en el que se cree que resolver el problema del logaritmo discreto es difícil. Decidir la pertenencia al lenguaje es trivial, ya que cada está en . Sin embargo, encontrar el testigo tal que se cumpla corresponde a resolver el problema del logaritmo discreto. ${\displaystyle \langle g\rangle }$${\estilo de visualización g}$${\displaystyle L=\{x\mid g^{w}=x\}}$${\estilo de visualización x}$${\displaystyle \langle g\rangle }$${\estilo de visualización w}$$Estilo de visualización g^{w}=x$

Una de las pruebas de conocimiento más simples y frecuentemente utilizadas, la prueba de conocimiento de un logaritmo discreto , se debe a Schnorr. ^[3] El protocolo está definido para un grupo cíclico de orden con generador . $Estilo de visualización Gq$${\estilo de visualización q}$${\estilo de visualización g}$

Para demostrar el conocimiento de , el demostrador interactúa con el verificador de la siguiente manera: ${\displaystyle x=\log _{g}y}$

1. En la primera ronda, el probador se compromete con la aleatoriedad ; por lo tanto, el primer mensaje también se llama compromiso .${\estilo de visualización r}$${\displaystyle t=g^{r}}$
2. El verificador responde con un desafío elegido al azar.${\estilo de visualización c}$
3. Después de recibir , el probador envía el tercer y último mensaje (la respuesta ) reducido módulo el orden del grupo.${\estilo de visualización c}$${\displaystyle s=r+cx}$

El verificador acepta, si . ${\displaystyle g^{s}=ty^{c}}$

Podemos ver que esta es una prueba de conocimiento válida porque tiene un extractor que funciona de la siguiente manera:

1. Simule el probador para obtener la salida . El probador ahora está en el estado .${\displaystyle t=g^{r}}$${\estilo de visualización Q}$
2. Generar un valor aleatorio e ingresarlo al probador. El resultado es .$estilo de visualización c_{1}$$Estilo de visualización s_{1}=r+c_{1}x$
3. Rebobine el probador hasta el estado . Ahora genere un valor aleatorio diferente e introdúzcalo en el probador para obtener .${\estilo de visualización Q}$$Estilo de visualización c_{2}$$Estilo de visualización s_{2}=r+c_{2}x$
4. Producción .${\displaystyle (s_{1}-s_{2})(c_{1}-c_{2})^{-1}}$

Dado que , la salida del extractor es precisamente . ${\displaystyle (s_{1}-s_{2})=(r+c_{1}x)-(r+c_{2}x)=x(c_{1}-c_{2})}$${\estilo de visualización x}$

Resulta que este protocolo es de conocimiento cero , aunque esa propiedad no es necesaria para una prueba de conocimiento.

Los protocolos que tienen la estructura de tres movimientos anterior (compromiso, desafío y respuesta) se denominan protocolos sigma . ^[4] El nombre se origina de Sig, en referencia al zigzag que simboliza los tres movimientos del protocolo, y MA, una abreviatura de "Merlin-Arthur". ^[5] Los protocolos sigma existen para probar varias afirmaciones, como las relacionadas con los logaritmos discretos. Usando estas pruebas, el demostrador no solo puede probar el conocimiento del logaritmo discreto, sino también que el logaritmo discreto tiene una forma específica. Por ejemplo, es posible probar que dos logaritmos de y con respecto a las bases y son iguales o cumplen alguna otra relación lineal . Para a y b elementos de , decimos que el demostrador prueba el conocimiento de y tales que y . La igualdad corresponde al caso especial donde a  = 1 y b  = 0. Como se puede calcular trivialmente a partir de esto es equivalente a probar el conocimiento de una x tal que . $estilo de visualización y_{1}$$estilo de visualización y_{2}$$estilo de visualización g_{1}$$estilo de visualización g_{2}$ $Estilo de visualización Zq$$estilo de visualización x_{1}}$$estilo de visualización x_{2}}$${\displaystyle y_{1}=g_{1}^{x_{1}}\land y_{2}=g_{2}^{x_{2}}}$$Estilo de visualización x_{2}=ax_{1}+b$$estilo de visualización x_{2}}$$estilo de visualización x_{1}}$${\displaystyle y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}}$

Ésta es la intuición detrás de la siguiente notación, ^[6] que se utiliza comúnmente para expresar exactamente lo que se demuestra mediante una prueba de conocimiento.

${\displaystyle PK\{(x):y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}\},}$

establece que el demostrador conoce una x que cumple la relación anterior.

Las pruebas de conocimiento son una herramienta útil para la construcción de protocolos de identificación y, en su variante no interactiva, de esquemas de firma. Dichos esquemas son:

• Firma de Schnorr

También se utilizan en la construcción de sistemas de firma grupal y credenciales digitales anónimas .

• Protocolo criptográfico
• Prueba de conocimiento cero
• Sistema de prueba interactivo
• Temas de criptografía
• Prueba de contraseñas de conocimiento cero
• Solidez (prueba interactiva)