Aprende a pensar como los criptógrafos

Demostrar sin ver

La gran aportación a la criptografía de Shafi Goldwasser y Silvio Micali es el Zero Knowledge Proof (ZKP), el 'protocolo de conocimiento cero'. La genialidad de su método es que permite que una parte pruebe a otra que una declaración es cierta sin mostrar dicha declaración. Su método es determinante en el mundo del big data. Por ejemplo, para compartir wwwdatos médicos sin que nadie llegue a 'verlos' realmente, sin que dejen de ser privados. Pero también para cerrar acuerdos comerciales sin notarios de por medio.

Acertijo 1: Alice y Bob

El ZKP es un complejo protocolo matemático, pero se explica con un ejemplo sencillo: el de 'Alice y Bob en la cueva de Ali Baba'. [Alice y Bob son nombres inventados por Ron Rivest y que los matemáticos de todo el mundo usan en lugar de A y B, para 'humanizar' los problemas].

Ampliar

Alice quiere demostrarle a Bob que sabe el conjuro que abre una puerta secreta, pero quiere hacerlo sin decirle a su amigo cuáles son esas palabras mágicas.

La puerta está en la cueva de Ali Baba, que tiene una entrada [A] y una bifurcación [B]: según el camino que se tome, se llega a la puerta por un lado u otro [C o D]. Alice entra en la cueva y asegura que, dado que sabe las palabras mágicas, cuando Bob llegue a la puerta -vaya por el lado que vaya-, ella estará siempre en el mismo lado que él. Recordemos que, como ella sabe las palabras mágicas, puede abrir la puerta cuando quiera.

Cuando Bob entra en la cueva y llega al punto [B], informa a Alice del camino que va a tomar: por la izquierda o por la derecha. Si entra por el mismo lado en el que ella está, Alice lo espera allí. Pero si entra por el lado contrario, ella usa las palabras mágicas para abrir la puerta, apareciendo en el lado correcto. Bob llega a la puerta y encuentra a Alice. Si la prueba se realizara solo una vez, podría ser por suerte. Pero si Alice lo hace muchas veces, empieza a ser imposible que el azar sea la explicación. Si repitiera el protocolo mil veces, la probabilidad de que Alice acertara solo por azar sería infinitesimal. Así quedaría demostrado que Alice sabe las palabras mágicas, aunque no se las diga nunca a Bob.

Acertijo 2: Sé dónde está Wally

Hay otro ejemplo para ilustrar cómo se pueden demostrar cosas sin decirlas más sencillo, aunque menos 'riguroso'. Lo desafiamos...

Alice y Bob están jugando a '¿Dónde está Wally?'. Alice dice: «Sé dónde está Wally». Bob no la cree. ¿Cómo puede Alice probarle a Bob que identificó a Wally sin revelar su ubicación en el dibujo? Vale usar objetos o máquinas, pero no señalar su ubicación ni implicar a terceros.

Solución: Se necesitan una fotocopiadora y unas tijeras. Fotocopian la página, Alice recorta la imagen de Wally de la copia sin que Bob mire. Destruye el resto y muestra a Bob el recorte de Wally.

También te pueden interesar estos artículos...

Las llaves que protegen Internet y sus 14 guardianes

Alan Turing: el fantasma que inventó la informática