Criptografía cuántica «comercial», crackeada

Antes que nada, que quede claro la palabra comercial en el título. La criptografía cuántica sigue siendo imposible de crackear en teoría, el problema es la implementación.

Feihu Xu, Bing Qi y Hoi-Kwong Lo de la Universidad de Toronto dicen haber craqueado uno de los sistemas criptográficos comerciales.

El tema es así: las pruebas que dicen que la criptografía cuántica es imposible de crackear se basan en implementaciones perfectas que en la realidad no es posible realizar... siempre habrá ruido que introducirá errores. Por ello es que los dispositivos de criptografía deben tolerar cierto ruido. Varias pruebas dicen que si el error se mantiene por debajo del 20%, el mensaje sigue siendo seguro. Sin embargo esas pruebas sólo consideran el ruido ambiente, no consideran errores introducidos en la preparación del estado inicial (el que envía el emisor)... y allí es donde Xu, Qi y Lo hicieron su truco. Ellos afirman que debido a ese error extra un tercero puede interceptar algunos bits cuánticos, leerlos y volverlos a enviar de una manera que incrementa el error en sólo 19,7%, lo cual será tolerado ya que está por debajo del 20% permitido.

Este problema es fácil de resolver, es cuestión de considerar también el error introducido por el emisor en el cálculo de tolerancia. Pero el problema fue destapado: de la teoría a la práctica habrá siempre cosas que asumir y en esas asunciones es donde está la debilidad.

Conclusión:
El método criptográfico clásico One Time Pad es 100% seguro, es imposible de crackear, el problema es que para utilizarlo y que sea seguro, debe haber algún modo de distribuir las claves a utilizar, las cuales deben ser del mismo largo que el mensaje (para 100% de seguridad). Para hacer eso existen métodos de distribución de claves cuánticos que son 100% seguros, imposibles de crackear, el problema es que para implementarlo debe haber algún modo de realizar un dispositivo sin errores. Para hacer eso se utilizan técnicas de corrección de errores, y se demuestra que se puede tolerar hasta un 20% de error ambiente y sigue siendo 100% seguro, el problema son los otros errores que no se tienen en cuenta. Ahí es donde entra el crack.

Para leer más:

• El paper de Xu, Qi y Lo está disponible online: arXiv:1005.2376.
• Hay una nota sobre el tema en el blog «The Physics arXiv»: Commercial Quantum Cryptography System Hacked.
• Hay una nota sobre el tema también en Slashdot: Commercial Quantum Cryptography System Hacked.

Equivalencia de λ-cálculos algebraicos

Como ya adelanté anteriormente, con Simon Perdrix, Christine Tasson y Benoît Valiron tenemos un paper aceptado en el workshop Higer-Order Rewriting que se llevará a cabo en Edimburgo el 14 de Julio.

Ayer enviamos la versión final (extended abstract de 5 páginas + referencias) y subimos la versión completa (con todas las pruebas, 19 páginas) al arXiv.

En este paper lo que hacemos es probar que el Algebraic λ-Calculus de Lionel Vaux (λalg), el cual es un fragmento del differential λ-Calculus, puede simular el Linear-Algebraic λ-Calculus de Pablo Arrighi y Gilles Dowek (λlin), el cual es un candidato a λ-Calculus para computación cuántica, y también probamos la simulación inversa. Ambos cálculos permiten la combinación lineal de términos, sin embargo presentan diferencias a la hora de realizar las reducciones. Por ejemplo en λalg el término


reduce a


en cambio en λlin, ese mismo término reduce a


Las pruebas de simulación se basan en la observación de que esencialmente λlin es call-by-value mientras que λalg es call-by-name. La simulación en un sentido usa la idea de "thunks" y en el otro es una extensión del continuation passing style.

Este paper es un paso hacia probar la dualidad entre ambos cálculos.

Computational Complexity in a Nutshell

No estoy seguro de la traducción del título. "nutshell" es algo así como cáscara de nuez, y es un término utilizado para referirnos a que un tema esta explicado en forma breve pero completo a la vez. En este caso el tema sería Complejidad Computacional.

Complejidad computacional es un área de las ciencias de la computación teórica que estudia la dificultad de resolver problemas computacionales. La dificultad de un problema computacional se mide en términos de los recursos computacionales necesarios para resolver ese problema, por ejemplo, tiempo, memoria, conectividad en la red, número de procesadores etc. El objetivo principal es crear una clasificación (estricta) de problemas computacionales. Esa clasificación son las clases de complejidad. Por ejemplo, los problemas que no requieren mucho tiempo ni mucha memoria se les llama problemas de tipo P. Problemas que requieren mas tiempo, pero aun con poca memoria son NP, y así.

También existe la complejidad computacional cuántica, que estudia la complejidad de las máquinas cuánticas. Más adelante voy a preparar una entrada sobre el tema.

Me gustaría compartir una serie de cursos impartidos en UC Berkeley dictados por Luca Trevisan sobre complejidad computacional. Los materiales para su curso los fue distribuyendo via su propio blog. Fue capaz de explicar temas relativamente difíciles de una forma breve y a la vez clara. Simplemente me encanta las matemáticas de esta área, sin dudad una de las invenciones más bellas de la mente humana.

Clase 1 - Introducción

Clase 2 - P y NP

Clase 3 - Circuitos Booleanos

Clase 4 - La Jerarquía Polinomial

Clase 5 - La Jerarquía Polinomial

Clase 6 - Teorema de Karp-Lipton

Clase 7 - Teorema de Valiant-Vazirani

Clase 8 - Conteo Aproximado

Para más detalles sobre el área recomiendo el libro Computational Complexity: A Modern Approach. Este libro está muy actualizado, y explica los conceptos de una forma bien clara