Prueba de conocimiento

Clase de prueba interactiva

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: . ${\displaystyle x}$ ${\displaystyle L}$ ${\displaystyle W(x)}$ ${\displaystyle R=\{(x,w):x\in L,w\in 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: ${\displaystyle R}$ ${\displaystyle \kappa }$ ${\displaystyle P}$ ${\displaystyle 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)\in R}$ ${\displaystyle P}$ ${\displaystyle w}$ ${\displaystyle x}$ ${\displaystyle 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. ${\displaystyle E}$ ${\displaystyle {\tilde {P}}}$ ${\displaystyle {\tilde {P}}}$

Detalles sobre la definición

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 ${\displaystyle R}$ ${\displaystyle W(x)}$ ${\displaystyle x}$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle E}$ ${\displaystyle {\tilde {P}}}$ ${\displaystyle {\tilde {P}}}$ ${\displaystyle E^{{\tilde {P}}(x)}(x)\in 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. ${\displaystyle \bot }$ ${\displaystyle 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)}$ ${\displaystyle V}$ ${\displaystyle x}$ ${\displaystyle w}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle w}$ ${\displaystyle {\tilde {P}}}$ ${\displaystyle {\tilde {P}}}$ ${\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 , como por ejemplo o , puede verse como más fuerte que la solidez de las pruebas interactivas ordinarias . ${\displaystyle \kappa (x)}$ ${\displaystyle 2^{-80}}$ ${\displaystyle 1/\mathrm {poly} (|x|)}$

Relación con las pruebas interactivas generales

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 }$ ${\displaystyle g}$ ${\displaystyle L=\{x\mid g^{w}=x\}}$ ${\displaystyle x}$ ${\displaystyle \langle g\rangle }$ ${\displaystyle w}$ ${\displaystyle g^{w}=x}$

Protocolos

Protocolo Schnorr

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 . ${\displaystyle G_{q}}$ ${\displaystyle q}$ ${\displaystyle 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 . ${\displaystyle r}$ ${\displaystyle t=g^{r}}$
2. El verificador responde con un desafío elegido al azar. ${\displaystyle c}$
3. Después de recibir , el probador envía el tercer y último mensaje (la respuesta ) reducido módulo el orden del grupo. ${\displaystyle 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}}$ ${\displaystyle Q}$
2. Generar un valor aleatorio e ingresarlo al probador. El resultado es . ${\displaystyle c_{1}}$ ${\displaystyle 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 . ${\displaystyle Q}$ ${\displaystyle c_{2}}$ ${\displaystyle 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})}$ ${\displaystyle x}$

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

Protocolos Sigma

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 . ${\displaystyle y_{1}}$ ${\displaystyle y_{2}}$ ${\displaystyle g_{1}}$ ${\displaystyle g_{2}}$ ${\displaystyle Z_{q}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle y_{1}=g_{1}^{x_{1}}\land y_{2}=g_{2}^{x_{2}}}$ ${\displaystyle x_{2}=ax_{1}+b}$ ${\displaystyle x_{2}}$ ${\displaystyle 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.

Aplicaciones

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 .

Véase también

• 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)

Referencias

1. Shafi Goldwasser , Silvio Micali y Charles Rackoff . La complejidad del conocimiento de los sistemas de prueba interactivos. Actas del 17.° Simposio sobre la teoría de la computación , Providence, Rhode Island. 1985. Borrador. Resumen ampliado
2. Mihir Bellare , Oded Goldreich: Sobre la definición de pruebas de conocimiento. CRYPTO 1992: 390–420
3. CP Schnorr , Identificación eficiente y firmas para tarjetas inteligentes, en G Brassard, ed. Advances in Cryptology – Crypto '89, 239–252, Springer-Verlag , 1990. Lecture Notes in Computer Science, n.° 435
4. [1] Sobre los protocolos Sigma
5. [2] Diseño modular de protocolos criptográficos seguros y prácticos
6. Sistemas de prueba para afirmaciones generales sobre logaritmos discretos