La prueba de Conocimiento Cero o Nulo.

interrogation¿Se puede demostrar que estamos en lo correcto sin tener que demostrar por qué lo estamos?
La respuesta es: Sí.

Supongamos que deseo demostrar que vos tenés una cantidad igual (o no) de monedas en cada bolsillo (derecho e izquierdo). Puedo pedírtelas, contarlas y así demostrar que tenés (o no) la misma cantidad en cada bolsillo.
Luego, demuestro por qué tengo razón tan sólo mostrando las monedas de cada bolsillo.
En este caso, violé tu derecho a la privacidad. No tengo por qué saber cuantas monedas tenés.

Aplicaré un ejemplo muy simple de la Prueba de Conocimiento Cero (PCC)[1]. Supongamos que en tu bolsillo derecho tenés X monedas, y en el izquierdo Y monedas. No pretendo conocer X ni Y para no violar tu derecho a la privacidad. Te voy a pedir que pienses (y no me digas) un número Z, preferentemente entero y mayor a X y a Y.
Te voy a pedir que me digas las diferencias entre Z y X; y la diferencia entre Z e Y. Si ambas diferencias son iguales, tenés la misma cantidad de monedas en cada bolsillo, si no, puedo saber dónde tenés más monedas; será donde la diferencia sea mayor.

O sea que tenemos dos ecuaciones:

Z – X = A

Z – Y = B

Dos ecuaciones con tres incógnitas (X, Y, Z), por lo tanto no puedo resolver y saber el valor de X ni el de Y. Sabiendo los valores de A y B, puedo demostrar en qué bolsillo tenés más monedas (valores de A y B diferentes, y por lo tanto un valor es mayor al otro, lo que me indica qué bolsillo tiene más monedas), o si en ambos tenés la misma cantidad (caso de A = B).
Así, demuestro lo que deseo sin demostrar por qué tengo razón, o sea, sin meterme donde no debo.

El PCC se usa mucho en Internet, por ejemplo en el juego Dónde está Waldo[2]

En relación a la verificación de las ojivas nucleares, no se puede observar qué hay en su interior para verificar que estén dentro de lo reglamentado, porque se viola el derecho de privacidad. Las Naciones que las poseen, no desean que se vea la tecnología ni otros detalles. De esta manera, se usa un sofisticado PCC, basados procedimientos que involucran valores aleatorios.


Referencias:

  1. http://es.wikipedia.org/wiki/Prueba_de_conocimiento_cero
  2. http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/waldo.html

Fuentes:

pdp.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s