Prueba de conocimiento cero

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En criptografía , un protocolo de conocimiento cero o prueba de conocimiento cero es un protocolo criptográfico que establece un método interactivo para una de las partes para probar a otra que una declaración (generalmente matemática) es cierta, sin revelar nada más que la veracidad de la declaración.

Ejemplo abstracto[editar]

Peggy toma al azar cualquier camino A o B, mientras que Víctor espera afuera.
Peggy toma al azar cualquier camino A o B, mientras que Víctor espera afuera.
Víctor elige una vía de salida.
Víctor elige una vía de salida.
Peggy aparece en los nombres de salida de Víctor.
Peggy aparece en los nombres de salida de Víctor.

Hay una historia bien conocida presentando algunas de las ideas de pruebas de conocimiento cero, publicado por primera vez por Jean-Jacques Quisquater y otros en su artículo "Cómo explicar pruebas de conocimiento cero a tus hijos".[1] Es una práctica común para etiquetar las dos partes en una prueba de conocimiento cero como Peggy (el probador de la declaración, prover) y Victor (el verificador de la declaración, verifier).

En esta historia, Peggy ha puesto al descubierto la palabra secreta que se utiliza para abrir una puerta mágica en una cueva. La cueva tiene forma de círculo, con la entrada en un lado y el bloqueo de la puerta mágica al otro lado. Víctor dice que va a pagarle por el secreto, pero no hasta que esté seguro de que ella realmente lo sabe. Peggy dice que va a decirle el secreto, pero no hasta que se recibe el dinero. Ellos establecen un plan por el cual Peggy puede demostrar que conoce la palabra sin decírsela a Víctor.

En primer lugar, Víctor espera fuera de la cueva mientras que Peggy ingresa. Ellos etiquetan los caminos a la izquierda y derecha de la entrada A y B. Peggy toma al azar cualquier camino A o B. A continuación, Víctor entra en la cueva y grita el nombre de la ruta en la que quiere que Peggy regrese, ya sea A o B, elegidos al azar. Proporcionar que ella realmente conoce la palabra mágica es fácil: ella abre la puerta, si es necesario, y vuelve a lo largo de la trayectoria deseada. Tenga en cuenta que Víctor no sabe cuál es el camino que se ella ha elegido.

Sin embargo, supongamos que no conocía la palabra. Entonces, sólo sería capaz de volver por el camino si Victor diese el nombre de la misma ruta por la que ella había entrado. Dado que Victor elegiría A o B al azar, habría una probabilidad del 50% de acertar. Si tuviera que repetir este truco muchas veces, por ejemplo 20 veces seguidas, su probabilidad de éxito sería prácticamente nula.

Por lo tanto, si Peggy fiablemente aparece en la salida que Víctor nombra, se puede concluir que es muy probable que conozca la palabra secreta.

Definición[editar]

Una prueba de conocimiento cero deben satisfacer tres propiedades:

  1. Totalidad: si la afirmación es verdadera, el verificador honesto (es decir, uno siguiendo el protocolo correctamente) se convence de ello por un probador honesto.
  2. Solvencia: si la declaración es falsa, no existe un probador engañoso que pueda convencer al verificador honesto de que es verdad, excepto con alguna probabilidad pequeña.
  3. Conocimiento cero: si la afirmación es verdadera, un verificador engañoso no aprende otra cosa mas que este hecho. Esto se formaliza mostrando que cada verificador engañoso tiene algún simulador que, teniendo en cuenta sólo la declaración a ser demostrada (y sin acceso al probador), puede producir una transcripción que "parece" una interacción entre el probador honesto y el verificador tramposo.

Los dos primeros de estas son las propiedades más generales de los sistemas de prueba interactivos . El tercero es lo que hace la prueba de conocimiento cero.

Las pruebas de Cero-conocimiento no son pruebas en el sentido matemático del término, porque hay una probabilidad pequeña, el error de solidez (soundness error), de que un probador engañoso será capaz de convencer al verificador de una declaración falsa. En otras palabras, que son probabilistas y no deterministas. Sin embargo, hay técnicas para disminuir el error de la solidez a valores insignificantes.

Una definición formal de conocimiento cero tiene que usar algún modelo computacional, la más común es la de una máquina de Turing . Sean P,V y S máquinas de Turing. Un sistema de prueba interactiva con (P,V) para un lenguaje L es de conocimiento cero, si para cualquier tiempo polinomial probabilístico (PPT) verificador \hat V existe un simulador PPT esperado S tal que:

              \forall x \in L, z \in \{0, 1\}^{*},   View_{\hat V} [P(x) \leftrightarrow \hat V(x, z)] = S(x, z)

El probador P se modela teniendo un poder de cálculo ilimitado (en la práctica, por lo general es una máquina de Turing probabilística). Intuitivamente, la definición establece que un sistema de prueba interactiva (P,V) es de cero-conocimiento, si por cualquier verificador \hat V existe un simulador de S eficiente que puede reproducir la conversación entre P y \hat V en cualquier entrada. La cadena de auxiliar z en la definición desempeña el papel de "conocimiento previo". La definición implica que \hat V no puede utilizar ningún conocimiento previo z para extraer información de su conversación con P, porque se demanda que S también tiene este conocimiento previo, entonces puede reproducir la conversación entre \hat V igual que antes.

La definición que se da es el de perfecto conocimiento cero. El conocimiento cero computacional se obtiene al exigir que las opiniones de los supervisores \hat V y el simulador sean computacionalmente indistinguibles , dada la cadena auxiliar.

Véase también[editar]

Notas[editar]

  1. «How to Explain Zero-Knowledge Protocols to Your Children». Advances in Cryptology - CRYPTO '89: Proceedings 435:  pp. 628–631. 1990. http://www.cs.wisc.edu/~mkowalcz/628.pdf. 

Enlaces externos[editar]