12 de septiembre de 2013

Estrenándome en Criptografía

Estoy terminando de escribir mi primer paper en criptografía. Aún no lo voy a hacer público (vía arXiv). Primero lo voy a mandar a una conferencia en formato de Resumen Extendido. Después voy a preparar un versión larga para revista, y ahí recién lo voy a hacer público.

Pero ya que ahora estoy como que me puedo tomar un respiro, luego de estar un par de meses totalmente estancado, quiero explicar un poco sobre mi nueva área de investigación.

En concreto, estoy estudiando Protocolos de Cero Conocimiento (Zero-Knowledge Proof). En términos simples, es un juego. Hay dos jugadores, Alice y Bob, y Alice quiere convencer a Bob de que ella sabe algo, e.g., la demostración del Teorema X. Pero Alice le quiere convencer a Bob de que X es correcto sin mostrarle la demostración. La pregunta es ¿Cómo lo hace? ¿Cuál es la estrategia que Alice tiene usar para convencer a Bob?

A primeras, no parece cierto de que algo así sea posible. ¿Cómo voy a convencer a alguien de que algo es cierto, sin siquiera mostrarle que ese algo es cierto? Bueno, de hecho, es posible, y es posible hacerlo para cualquier conjunto en NP (asumiendo ciertas conjeturas de complejidad computacional). También, mostrar que esto es posible y de que es la definición correcta de seguridad, fue lo que valió para otorgar el premio Turing a Shaffi Goldwasser y Silvio Micali este año.

Estos protocolos de cero conocimiento lo que logran es que cualquier adversario, que trate de salirse del protocolo, no lo pueda hacer. Sus aplicaciones están principalmente en el diseño de protocolos criptográficos entre dos o más agentes, e.g., secure multiparty communication.