PDF de programación - Man in the Middle y los protocolos cuánticos

Man in the Middle y los protocolos cuánticos

Miguel Ángel López Muñoz

6 de noviembre de 2007

Índice
1. Introducción

2. La teoría cuántica

2.1. La mecánica cuántica .
.
2.2. La computación cuántica .
.
2.3. La información cuántica
2.4. La criptografía cuántica .
.

.

3. Conceptos básicos

3.1. El qubit
. . . . . . .
3.2. Múltiples qubits . . .
3.3. Notación de Dirac .
.
. .
3.4. Puertas cuánticas

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

4. Base del protocolo

Indistinguibilidad de qubits .
.

.
4.1.
4.2. No clonación . . . .
.
4.3. Distinguir entre qubits EPR y no EPR .
4.4. El ataque EPR Man in the Middle
.

.
.

.
.

.

.
.

.

.
.

.

.

.

.
.

5. Descripción del protocolo

6. Comentarios de diseño
6.1. Acerca del Paso 5 .
6.2. Acerca del Paso 1 .

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

1

2

2
.
2
.
3
. 10
.
11

16
. 16
.
17
. 18
. 19

21
. 21
22
.
23
.
.
24

25

27
. 27
. 28

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

6.3. Acerca del Paso 3 .
6.4. Acerca del Paso 4 .

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

. 31
. 32

1.

Introducción

Este trabajo pretende introducir un nuevo protocolo cuántico basado en pares
EPR para generar y compartir claves que no está afectado por el ataque llamado
EPR Man in the Middle. Este método de criptoanálisis, que posee múltiples vari-
antes incluso en criptografía clásica, ha demostrado ser tremendamente efectivo
en muchos de los protocolos basados en pares EPR que se han diseñado hasta
ahora. Añadimos también una serie de comentarios respecto a su diseño, además
de una introducción a la computación cuántica con los conceptos fundamentales
de la misma para facilitar su comprensión.

2. La teoría cuántica

Antes de empezar a hablar de la criptografía cuántica es mejor detenerse
primero en la computación cuántica y la información cuántica, dos ramas de estu-
dio recientes que, además de estar muy emparentadas con la criptografía cuántica,
ayudarán a mostrar qué puede aportar este nuevo enfoque.

2.1. La mecánica cuántica

La computación cuántica y la información cuántica son el estudio de las tareas
de proceso de información que pueden ser llevadas a cabo empleando sistemas
mecánicos cuánticos. Esta idea, tan simple en su concepción, está demostrando
ser tan profunda que gracias a ella se han obtenido resultados que se resistían a
ser descubiertos con las herramientas clásicas de las que se disponía hasta la fecha.
El motivo más importante de que esté ocurriendo esto es la base física sobre
la que se sustentan dichos estudios. Desde su descubrimiento a comienzos de los
años veinte, la mecánica cuántica no ha dejado de sorprender a los físicos. Su
nacimiento fue motivado por el hecho de que la física que existía hasta la fecha,
ahora conocida como física clásica, empezó a predecir una serie de fenómenos
que sencillamente no podían suceder, como electrones dando vueltas infinitamente
alrededor del núcleo del átomo. Al principio esto se solucionó añadiendo una serie
de nuevas hipótesis construidas de tal modo que la estructura general mantenía

2

coherencia, pero a medida que se sabía más acerca del átomo y la radiación esas
hipótesis estaban cada vez más comprometidas.

Se puede decir que la mecánica cuántica es un conjunto de reglas para la cons-
trucción de teorías físicas que conciernen al mundo de lo microscópico o atómico,
para ser más precisos. La mecánica cuántica ha permitido estudiar gran cantidad
de fenómenos aparentemente inconexos entre sí, como la fusión nuclear en las
estrellas, la estructura del átomo o los superconductores. Como muchos avances
revolucionarios en el mundo de la ciencia (como la teoría de la relatividad), las
normas por las que se rige son aparentemente sencillas pero a su vez encierran
una profunda complejidad debido al hecho de que se oponen a todo lo que hasta
entonces ha sido considerado al respecto. En el caso de la mecánica cuántica,
además, dan lugar a resultados que van en contra de la intuición.

Por ejemplo, a principios de los años ochenta, se intentó averiguar si era posi-
ble emplear resultados de mecánica cuántica para enviar una señal a mayor ve-
locidad que la de la luz, algo que sería imposible según la teoría de la relatividad
de Einstein. Un estudio más detallado en esta materia revela que resolver ese pro-
blema se reduce a conseguir clonar un estado cuántico desconocido a priori. Sin
embargo se sabe que es imposible copiar un estado cuántico arbitrario, un hecho
que no deja de ser chocante, ya que tanto en computación clásica como en teoría de
la información clásica realizar una copia de información es no sólo posible, sino
prácticamente trivial. Este sorprendente resultado revela que un potencial progra-
mador cuántico no podría emplear una instrucción tan sencilla como la reasig-
nación de una pieza de información, algo que sin duda resulta extremadamente
chocante para todo aquel que ha programado alguna vez en un ordenador. Este
resultado acerca de la no clonación de un estado cuántico es uno de los primeros
obtenidos en computación e información cuántica.

2.2. La computación cuántica

Para entender bien lo que es la computación cuántica primero hay que pararse
a pensar un momento en lo que es la computación clásica. En realidad, ya existían
ideas relativas a la computación mucho antes de que se inventara el primer orde-
nador. Uno de los primeros en introducirse sin saberlo en este área fue Leibnitz.
En el año 1686 escribe los llamados Discursos de Metafísica, pero no los llega a
publicar nunca, influenciado por la opinión del filósofo Arnauld, que al leer parte
de ellos se queda horrorizado. En la sección V y VI de esos discursos, Leibnitz
discute una cuestión crucial: ¿Cómo podemos distinguir un mundo que puede ser

3

explicado mediante la ciencia de otro que no puede ser explicado? ¿Cómo saber
que un determinado fenómeno que nos rodea obedece a una ley y cómo saber que
se debe a una conducta errática y aleatoria?

Leibnitz usa el ejemplo de las manchas de tinta en un folio. Si alguien mancha
un folio con salpicaduras de tinta y determina un conjunto de puntos en la página,
incluso aunque los puntos puedan ser descritos de manera completamente precisa
en términos matemáticos (usando, por ejemplo, interpolación de Lagrange) eso
no quiere decir que obedezcan ni mucho menos a una determinada ley. Es más,
Leibnitz razona que la curva obtenida sería tan difícil de estudiar como el propio
conjunto de puntos, con lo que el modelo que pudiéramos obtener carece por
completo de interés, puesto que no ayuda a simplificar el fenómeno observado.

Hay varios conceptos aquí que actualmente tienen mucho que ver con la teoría
de la computación. El primero de ellos es lo que se ha mencionado como ’difícil de
estudiar’. En teoría de la computación la palabra más correcta sería ’complejo’.
Leibnitz, de manera implícita, está diciendo que un problema (las manchas de
tinta) es complejo cuando cualquier explicación a ese problema no simplifica el
problema original.

El otro asunto es lo referente a ley y caos. Para Leibnitz algo es aleatorio
cuando no admite manera sencilla de ser explicado, de manera similar a como
se entiende en teoría de la información algorítmica. Puede que sea aleatorio de
verdad o puede que no, pero eso encaja bien en la definición porque desde nuestro
punto de vista ambos fenómenos resultan, no sólo igualmente incomprensibles,
indistinguibles entre sí.

Lo más importante de todo esto es que Leibnitz no empleó ninguna máquina
para llegar a tales conclusiones, sino que estudió la resolución de problemas desde
un punto de vista abstracto. Más tarde él mismo fabricó una de las primeras calcu-
ladoras existentes, además de ser uno de los primeros científicos en comprender
la importancia de la aritmética binaria. Pero el caso es que esas ideas están más
allá de las máquinas empleadas para comprobarlas.

Muchísimo más tarde de estas ideas, el matemático Alan Turing publicó un
artículo en 1936 en el que describía un aparato extremadamente sencillo llamado
la Máquina de Turing. La Máquina de Turing consiste, sin entrar en muchos de-
talles, en una cinta de longitud infinita en la que es posible escribir y sobreescribir
caracteres de un determinado alfabeto, borrar un carácter (que no es más que so-
breescribir el carácter ’en blanco’) y avanzar o retroceder a lo largo de la cinta.
Es fácil comprobar que versiones más complicadas de la Máquina de Turing, co-
mo aquellas que emplean más de una cinta, son completamente equivalentes a la

4

Máquina de Turing original, también conocida como Máquina de Turing Univer-
sal. Sin embargo el potencial de la Máquina de Turing va mucho más allá de eso,
y su propio creador postuló que cualquier problema que pudiera ser considerado
en términos algorítmicos podría ser resuelto utilizando una máquina de Turing,
con independencia del tiempo que tardara en hacerlo. Esta afirmación es conocida
como la Tesis de Turing-Church.

La Tesis de Turing-Church conecta dos conceptos distintos en computación.
Esos conceptos son la manera abstracta de resolver un problema y la manera
concreta de resolver un problema. Un algoritmo es una manera de resolver un
problema que puede tener distintas variantes según los medios reales de los que
dispongamos. Si un algoritmo dice que para hacer una tarta tengo que ir primero al
supermercado de las afueras a comprar los ingredientes, el problema se resolverá
de distinta manera si disponemos de