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 sabe algo. El significado de que una máquina "sabe algo" se define en términos de computación. Una máquina "sabe algo" si este algo puede ser computado, dado a la máquina como entrada. Dado que el programa del probador no necesariamente produce el conocimiento en sí (como ocurre con las pruebas de conocimiento cero ^{[ 1 ]} ), se introduce una máquina con un programa diferente, llamada extractor de conocimiento, para capturar esta idea. Nos interesa principalmente lo que pueden probar las máquinas con tiempo de ejecución polinomial . En este caso, el conjunto de elementos de conocimiento se limita a un conjunto de testigos de algún lenguaje en NP .

Dejar${\displaystyle x}$ser una declaración de lenguaje${\displaystyle L}$en NP y${\displaystyle W(x)}$el conjunto de testigos para x que deben ser aceptados en la prueba. Esto nos permite definir la siguiente relación:${\displaystyle R=\{(x,w):x\in L,w\in W(x)\}}$.

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

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

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

Dejar${\displaystyle R}$ser un pariente testigo,${\displaystyle W(x)}$el conjunto de todos los testigos de interés público${\displaystyle x}$, y${\displaystyle \kappa }$el error de conocimiento. Una prueba de conocimiento es${\displaystyle \kappa }$-válido si existe una máquina de tiempo polinomial${\displaystyle E}$, dado el acceso al oráculo a${\displaystyle {\tilde {P}}}$, de tal manera que para cada${\displaystyle {\tilde {P}}}$, es el caso que${\displaystyle E^{{\tilde {P}}(x)}(x)\in W(x)\cup \{\bot \}}$y${\displaystyle \Pr(E^{{\tilde {P}}(x)}(x)\in W(x))\geq \Pr({\tilde {P}}(x)\leftrightarrow V(x)\rightarrow 1)-\kappa (x).}$

El resultado${\displaystyle \bot }$significa que la máquina de Turing${\displaystyle E}$No se llegó a ninguna conclusión.

El error del conocimiento${\displaystyle \kappa (x)}$denota la probabilidad de que el verificador${\displaystyle V}$podría aceptar${\displaystyle x}$, aunque el probador en realidad no conoce a un testigo${\displaystyle w}$El extractor de conocimiento${\displaystyle E}$se utiliza para expresar lo que se entiende por el conocimiento de una máquina de Turing . Si${\displaystyle E}$puede extraer${\displaystyle w}$de${\displaystyle {\tilde {P}}}$, decimos que${\displaystyle {\tilde {P}}}$conoce el valor de${\displaystyle 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${\displaystyle \kappa (x)}$, como por ejemplo${\displaystyle 2^{-80}}$o${\displaystyle 1/\mathrm {poly} (|x|)}$, puede considerarse más fuerte que la solidez de las pruebas interactivas ordinarias .

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, probar la pertenencia a un lenguaje puede ser sencillo, mientras que calcular un testigo específico puede resultar difícil. Esto se explica mejor con un ejemplo:

Dejar${\displaystyle \langle g\rangle }$ser un grupo cíclico con generador${\displaystyle g}$en el que se cree que resolver el problema del logaritmo discreto es difícil. Decidir la pertenencia al lenguaje${\displaystyle L=\{x\mid g^{w}=x\}}$es trivial, como todo${\displaystyle x}$está en${\displaystyle \langle g\rangle }$Sin embargo, encontrar al testigo${\displaystyle w}$de tal manera que${\displaystyle g^{w}=x}$Esto corresponde a resolver el problema del logaritmo discreto.

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

• Firma de Schnorr

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

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