Protocolos de Conocimiento Cero




Interesante articulo reseñado en Kriptopolis: El rey se sentó en su trono, visiblemente preocupado y deseando no haber realizado nunca aquella apuesta. En un momento de debilidad, después de haber bebido más de la cuenta, su desmedida afición por el juego le había llevado a apostar con el monarca vecino que era capaz de demostrar cierto complicado teorema en menos de una semana. El mayor problema no era el hecho de que careciera de dicha demostración, puesto que en su apuesta no se decía que no pudiera recibir ayuda de los matemáticos de su país, sino que al proporcionársela al rey vecino, éste podría emplearla para construir cierto tipo de máquinas, que posteriormente utilizaría para declararle la guerra. Cuando el matemático más sabio del reino escuchó la historia se limitó a sonreir, con un brillo enigmático en la mirada... -Majestad -dijo-, podemos ganar la apuesta sin revelar la demostración." Aunque parezca chocante, el matemático de esta historia tiene razón. Existe un mecanismo que permite demostrar que se está en posesión de cierto conocimiento, sin necesidad de revelarlo: los protocolos de conocimiento cero. En este artículo explicaremos brevemente su fundamentación teórica, y apuntaremos algunas de sus más interesantes aplicaciones. Supongamos que David posee cierta información X y que Víctor quiere comprobar que realmente la tiene. Para ello David construye un problema matemático M, computacionalmente imposible de resolver, de forma que X constituya una solución para M (nótese que David parte de la solución para elaborar el problema). Un ejemplo válido podría ser el del logaritmo discreto: se escogen dos números a y n, y se calcula b= a^X (mod n). Entonces el enunciado de M sería: "calcular X como el logaritmo base a de b". Como los lectores asiduos de Kriptópolis bien sabrán, obtener la solución de M resulta intratable si los números involucrados son lo suficientemente grandes. Entonces se produce el siguiente diálogo: - David transforma M para construir un nuevo problema matemático M', cuya solución X' se podrá calcular fácilmente a partir de X, y lo envía a Víctor. - Víctor genera un bit aleatorio B y lo remite a David. - Si: * B=0, David demuestra la relación entre M y M', sin dar la solución a M'. * B=1, David proporciona la solución X' del problema M', sin revelar la relación entre M y M'. Si observamos el protocolo con atención, vemos que la única forma de que David pueda responder correctamente a ambas preguntas es que posea la solución X. El meollo de la cuestión es que David únicamente revela, o bien la relación entre M y M', o bien el valor de X', y que cada una de estas cosas por separado resulta inútil para calcular X. Obviamente, David podría engañar a Víctor en el 50% de los casos. Pero, ¿y si se repite la "conversación" con diferentes valores de M' y B un número m veces? Pues que la probabilidad de que David engañe a Víctor es exactamente de 1/(2^m). Por ejemplo, con diez repeticiones, Víctor tendría una certeza del 99.9% sobre que David realmente posee el secreto... ¡y todo ello sin revelar ninguna información útil para que Víctor conozca el valor de X! Existen muchos problemas matemáticos susceptibles de ser empleados como base para un protocolo de conocimiento cero. Uno de ellos es el del homomorfismo de grafos. Un grafo es un conjunto de puntos o nodos conectados entre sí por arcos. Pues bien, dados dos grafos con el mismo número de nodos, averiguar si reordenando los nodos de uno se puede quedar exactamente igual que el otro (son homomorfos), es un problema computacionalmente intratable. Para emplear protocolo de conocimiento cero basado en grafos, David partiría de un grafo G1, y reordenando los nodos calcularía G2, de forma que únicamente él conoce la correspondencia entre los nodos de G1 y los de G2. El protocolo sería: - David reordena los nodos de G1, y obtiene H, que será homomorfo a G1 y G2. - Víctor genera el bit aleatorio B. - David envía a Víctor la correspondencia entre G1 y H si B=1, o la correspondencia entre G2 y H si B=0. Obsérvese que para conocer la correspondencia entre G1 y G2, son necesarias simultáneamente las correspondencias entre G1 y H, y entre H y G2. Puesto que David únicamente revela una de las dos, el protocolo funciona. De hecho, está matemáticamente demostrado que la demostración de un teorema se puede reducir a encontrar un homomorfismo entre grafos, lo cual permitió al rey de nuestra historia ganar la apuesta y evitar la guerra. El tema de los protocolos de conocimiento cero es extremadamente interesante y ciertamente complejo. Existen múltiples variantes, incluso algunas no interactivas, que permiten adaptarlos a infinidad de situaciones. De hecho, proporcionan un mecanismo de identificación de bajos requerimientos computacionales, susceptible de ser empleado en tarjetas inteligentes. Sin embargo, la que quizás sea la más prometedora de sus aplicaciones es el voto electrónico: sería posible demostrar que uno ha votado correctamente, y contabilizar su voto, sin necesidad de revelar su contenido. Debido a su especial interés, exploraremos esta aplicación con más detalle en posteriores artículos.
Manuel Lucena
wwwdi.ujaen.es/~mlucena
Fuente: Kriptopolis


Otras artículos de interés:

Cómo formatear una memoria USB en FAT16
1. Instalar las utilidades para formatear con el siguiente comando (desde Terminal de root): apt-get install dosfstools 2. Conocer la ubicación del dispositivo con el siguiente comando: ...
Guía de operaciones de seguridad para Windows 2000 Server (PARTE III)
Asegurar servidores basándose en su función. En el capítulo anterior, observamos cómo se puede usar una directiva de grupo para definir la configuración de seguridad en los servidores. En este capítulo, veremos aspectos más específicos, com...
Instalar Tor y configurar Privoxy para mantener la privacidad en la navegación en Ubuntu
1. Abrir un Terminal de root en Aplicaciones>Accesorios>Terminal de root o escribiendo gksu gnome-terminal en el cuadro que aparece al utilizar la combinación Atl+F2 2. Instalo Tor con el siguiente comando (se instalará también Pr...
Cortafuegos (Firewall)s: Test de fugas
Es fácil disponer de un cortafuegos que evite que otros equipos inicien y establezcan conexiones al nuestro. Sin entrar en más detalles, cualquier cortafuegos es capaz de eso con más o menos grado de sofisticació...
Mejorar rendimiento en Chrome / Chromium
Ojo: en algunos SO puede causar inestabilidad, pero puede ser facilmente restaraurados. Lea la acción que realiza cada tag, allí explican. Dicho esto: Abrimos Chrome | Chromium Escribir la barra de navegación: chrome://fla...
Netstat Una herramienta Desconocida
Una de las herramientas menos conocidas por el usuario y muy usada por las personas que tienen algún conocmiento es Netstat que nos va a permitir comprobar si tenemos algun puerto abierto y por lo tanto, hacernos sospechar de que alguien puede estar...
Actualizar al Kernel 3.8 en Ubuntu / LinuxMint
Entre las novedades de este Kernel: Soporte OpenGL en los controladores Nouveau y mejoras en la gestión de memoria RAM. Implementación de soluciones para evitar fallo de arranque en sistemas HP. ...
centOS: ERROR! MySQL is not running, but lock file (/var/lock/subsys/mysql)
Se soluciona facilmente con: rm /var/lock/subsys/mysql Ojo, debe ser root ahora; /etc/init.d/mysql start luego /etc/init.d/mysql stat...
Añadir soporte USB en VirtualBox
Añadelo primero en la pestaña de configuración de VirtualBox en donde esta USB luego por consola sudo usermod -a -G vboxusers 'usuario' donde usuario es tu nombre de usuario Com...
Instalar / Configure Varnish en CentOS 6.5
Varnish Cache es un acelerador de aplicaciones web, también conocido como caché de proxy HTTP inversa. Se instala delante de cualquier servidor HTTP y se configura para almacenar en caché una copia del recurso solicitado. Idea...

Brindanos
un o una


Redes Sociales

Publicidad


Gana Bitcoins desde tu casa

Categorías


Planeta Vaslibre

Blog Roll




Nube de tags

  • anonimato
  • anonimo
  • antivirus
  • apache
  • blog
  • bsd
  • bug
  • centos
  • cero
  • chrome
  • cifrado
  • computer
  • conocimiento
  • debian
  • exploits
  • fedora
  • fice
  • firefox
  • forense
  • freebsd
  • gentoo
  • github
  • gnome
  • gnu
  • gpl
  • gtk
  • hack
  • hacking
  • hosting
  • informatica
  • internet
  • isos
  • libre
  • licencias
  • linux
  • linuxmint
  • lxde
  • micros
  • mint
  • mit
  • mozilla
  • mysql
  • noticia
  • opensource
  • pgp
  • php
  • protocolos
  • sabayon
  • seguridad
  • system
  • tecnologia
  • thunar
  • thunderbird
  • tor
  • troyanos
  • tware
  • ubuntu
  • underground
  • vaslibre
  • virus
  • viserproject
  • vivaldi
  • vulnerabilidades
  • web
  • website
  • windows
  • xanadu
  • xfce
  • xombra