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:

Monitorizar ancho de banda en Ubuntu
El Ancho de banda en redes es la velocidad de datos con la que se mueven los datos dentro de una conexión. Cuanto mayor sea la capacidad, es probable que poseas un rendimiento mejor aunque influyen otros factores. En Ubuntu...
Instalar Ecualizador de Sonido en Linux - Debian - LinuxMint - Xanadu
PulseAudio (antiguamente PolypAudio) es un servidor de sonido multiplataforma, capaz de funcionar por red. Funciona bajo sistemas compatibles con POSIX como GNU/Linux y también en otros sistemas operativos como Microsoft Windows. Para m...
Actualizar al Kernel 3.7 en Ubuntu / LinuxMint
Entre las novedades de este Kernel .- soporte de la tecnología Network Address Translation (NAT) para el protocolo IPv6 .- inclusión de cambios importantes en los controladores para el hardware gráfico de Int...
Encriptación WPA en Ubuntu
Una de las formas de encriptar una red wireless es usar encriptación WPA. Este método de encriptación es una evolución del ...
Instalar Kernel 3.19 en Ubuntu | Linux Mint
Mejoras: Soporte para ARM Soporte para Coresight Mejoras de importancia en el soporte para la gestión de energía y para ACPI Soporte para el algoritmo de compresión LZ4 Mejoras en el soporte para RAID 5 y 6 ...
Instalando Adobe AIR Linux Alpha en Ubuntu
Adobe® AIR™ es un tiempo de ejecución de sistema operativo cruzado que permite a los desarrolladores utilizar tecnologías web familiares, entre las que se incluyen HTML, Ajax...
Cómo defender a su empresa de la ingeniería social
La ingeniería social es una de las técnicas de hacking más antiguas de la informática –casi tanto como ella misma– con la que un hacker puede penetrar hasta en los sistemas más difíciles usando la vulnerabilidad más grave de todas: la huma...
Monografía de Sistemas Operativos
Indice 1. Introducción 2. Tipos de Sistemas Operativos 3. Sistemas de Archivos 4. Administración de la Memoria 5. Administración de Procesos 6. Principios en el Manejo de Entrada - Salida 7. Núcleos de Sist...
Normas de etiqueta en la Red
La Netiquette es una serie de reglas de etiqueta que todos debemos conocer y seguir al comunicarnos a través de la red para una comunicación más efectiva y un mejor uso de los recursos y el tiempo. Debido a las características particulares del me...
Protecciones extras y optimizaciones para nuestro Linux
Unas de las cosas geniales de cualquier distribución linux es que podemos mejorar optimizar su configuración por defecto. Para ello en esta oportunidad editaremos: el archivo: /etc/sysctl.conf Abrimos la consola: ...

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