Curso: Computación y Criptografía Cuántica


Lección 2. Criptografía Cuántica
Dra. Alfonsa García, Dr. Francisco García, Dr. Jesús García - 24/06/2014


En esta lección se presenta una de las aplicaciones más importantes de la teoría de la información cuántica. Como hemos visto, el algoritmo de Shor abre la posibilidad de que los ordenadores cuánticos puedan romper la seguridad de los criptosistemas de clave pública. Afortunadamente la criptografía cuántica proporciona un sistema seguro de distribución de claves privadas.

El curso completo se compone de tres lecciones:

  Lección 1. Modelo de Computación Cuántica
  Lección 2. Criptografía Cuántica
  Lección 3. Algoritmos Cuánticos

Si deseas descargar las diapositivas del curso en formato pdf, o las soluciones a los ejercicios propuestos, puedes hacerlo desde esta dirección del Material de GIEMATIC (Grupo de innovación educativa).

Los tres vídeos de apoyo a las lecciones de este MOOC presentados por el Dr. Jesús García, son los siguientes:

Seminario de introducción a la Computación y Criptografía Cuántica: 1

Seminario de introducción a la Computación y Criptografía Cuántica: 2

Seminario de introducción a la Computación y Criptografía Cuántica: 3

También puedes ver estos vídeos del "Seminario de Introducción a la Computación y Criptografía Cuántica" directamente en YouTube desde sus correspondientes enlaces:

Seminario de introducción a la Computación y Criptografía Cuántica: 1
Seminario de introducción a la Computación y Criptografía Cuántica: 2
Seminario de introducción a la Computación y Criptografía Cuántica: 3

El tiempo recomendado para el seguimiento de esta lección y la realización de actividades propuestas es de 10 horas semanales durante dos semanas. Puedes ampliar la información consultando el libro Quantum Computation and Quantum Information [6].

Temario

Objetivos

  • 1. Entender las implicaciones que podría tener la la construcción de ordenadores cuánticos en la seguridad de los criptosistemas de clave pública, así como las posibilidades que ofrecen las leyes de la mecánica cuántica para garantizar protocolos seguros de distribución de claves privadas.
  • 2. Conocer el protocolo BB84 y analizar su seguridad, desde el punto de vista de la computación.
  • 3. Conocer algunos otros protocolos cuánticos de distribución de claves.

APARTADO 2.1. EL PROBLEMA DE LA COMUNICACIÓN SEGURA

La criptografía es una ciencia tan antigua como la humanidad, ya que desde siempre los individuos han necesitado comunicarse de modo seguro y han ideado métodos para ocultar sus mensajes a posibles espías, mediante procedimientos de cifrado.

img/L2_F1.jpg

La criptografía clásica se puede dividir en dos grandes ramas: criptografía simétrica o de clave privada y criptografía asimétrica o de clave pública.

img/L2_F2.jpg img/L2_F3.jpg

Cuestiones para reflexionar e investigar:
Haz un esquema comparando las ventajas e inconvenientes de los criptosistemas asimétricos y los simétricos.

Uno de los problemas de mayor dificultad práctica a la hora de llevar a cabo una comunicación segura mediante un sistema de clave privada es la distribución y almacenamiento de las claves. Un resultado de Shannon de 1949 establece que si la clave es aleatoria, de la misma longitud que el mensaje a cifrar y se usa una única vez, el cifrado es seguro. De hecho es el único sistema cuya seguridad ha sido probada. Sin embargo, la necesidad de distribuir y almacenar de manera segura las claves, en general largas y de un solo uso, limita claramente las posibilidades de este sistema.

Una de las ventajas de los sistemas de clave pública es que permiten prescindir de acordar y distribuir la clave secreta. Sin embargo, la seguridad de estos sistemas nunca ha sido probada matemáticamente. No se sabe si factorizar un número puede hacerse en tiempo polinómico, simplemente no se ha encontrado un algoritmo que lo haga, de modo que la seguridad práctica del sistema RSA viene proporcionada por el coste computacional de la factorización. La construcción de un ordenador cuántico en el que se implemente el algoritmo de Shor, que permite calcular logaritmos discretos y factorizar números enteros en tiempo polinómico, supondría claramente la fractura definitiva de los sistemas de clave pública más importantes.

Las leyes de la mecánica cuántica, sin embargo, proporcionan un medio para abordar el problema de la distribución segura de claves privadas. Esencialmente consiste en que los comunicantes se transmiten la clave privada a través de un canal cuántico (por ejemplo un cable de fibra óptica, si la clave se codifica mediante estados de polarización de fotones). La aportación cuántica a la seguridad del proceso es que un espía no puede extraer información sin revelar su presencia a los comunicantes, ya que al medir estados cuánticos éstos se modifican irreversiblemente y además los estados cuánticos no se pueden copiar.

Existen diferentes protocolos cuánticos de distribución de claves denominados QKD (Quantum Key Distribution), ideados con el fin de intercambiar claves privadas de un solo uso, que se pueden usar en sistemas simétricos de seguridad. Estos protocolos, se pueden llevar a cabo con tecnología actual. De hecho, la llamada criptografía cuántica es la primera aplicación comercial de la mecánica cuántica.

En un proceso de distribución cuántica de claves intervienen un emisor y un receptor, comúnmente denominados Alicia y Bob, junto con un espía, Eva, y dos canales de comunicación, uno cuántico para enviar fotones y otro clásico para reconciliar y depurar información.
Eva puede acceder al canal clásico, que estará autenticado, por lo que tiene acceso a la información pero no puede suplantar a Alicia o Bob.
También puede acceder al canal cuántico y usar todos los medios que desee con la única restricción de que sean compatibles con las leyes de la mecánica cuántica. Los dos comunicantes legítimos (Alicia y Bob) van a usar un trozo de su clave para detectar la presencia de Eva.
img/L2_F4.jpg

APARTADO 2.2. PROTOCOLO BB84

Los estados de polarización de un fotón se pueden usar para diseñar un sistema criptográfico cuántico de un solo uso.

En el espacio de Hilbert H1 consideraremos las dos bases ortogonales más usuales: la base B1=[|0>,|1>], que se identifica con la polarización horizontal y vertical, y la base BX=[|+>,|->], identificada con la polarización 45º y -45º.

En la siguiente imagen se recuerda el resultado que se puede obtener al medir, con cada una de estas bases, los cuatro estados de ambas.

img/L2_F5.png

Uno de los esquemas más sencillos para la generación y distribución de una clave aleatoria es el protocolo BB84 [3], propuesto en 1984 por Bennett y Brassard, que se puede describir del siguiente modo:

Paso 1: Alicia genera una cadena aleatoria de ceros y unos (por ejemplo lanzando una moneda al aire).

Paso 2: Para cada bit de la cadena, Alicia elige aleatoriamente una de las dos bases B1 o BX y envía a Bob, por un canal cuántico, el qubit correspondiente, mediante un fotón polarizado, de acuerdo con el siguiente alfabeto:

  • Si ha elegido B1: el 0 lo codifica como |0> (polarización horizontal) y el 1 como |1> (polarización vertical).
  • Si ha elegido BX: el 0 lo codifica como |+> (polarización 45º) y el 1 como |-> (polarización-45º).

Cuando Bob recibe cada fotón, no tiene modo de saber con qué alfabeto ha sido codificado, así que él lo mide eligiendo, también aleatoriamente, para cada uno de ellos la base B1 o BX. Aproximadamente la mitad de las veces Bob elegirá la misma base que Alicia y la otra mitad elegirá la base contraria a la utilizada por ella.

Paso 3: Para localizar y eliminar los bits en que las mediciones se han realizado con distintas bases, se realiza el proceso de contraste de información, denominado siftting o Reconciliación de bases.

Bob comunica a Alicia, por el canal clásico, qué base ha usado en cada medición.
Como respuesta, Alicia le comunica las posiciones en las que ella ha usado la misma base. En estas posiciones, Alicia y Bob deben tener bits coincidentes.
img/L2_F7.jpg

Paso 4: Alicia y Bob borran de sus cadenas los bits en los que se han usado bases diferentes y se quedan con el resto. De este modo, si no ha habido ruidos ni interferencia de espías, tienen una clave común, que denominamos clave bruta, cuya longitud será aproximadamente la mitad de la de la cadena inicial.

img/L2_F8.jpg

Ejercicio 2.2.1
Suponiendo que se ha llevado a cabo el protocolo BB84, sin espías ni interferencias, ¿por qué se puede asegurar que la clave bruta es común y que su longitud es aproximadamente la mitad de la de la cadena inicial?

Si ha habido espías, cualquier estrategia de espionaje va a introducir discrepancias en la clave de Bob. Por ello, para detectar la presencia de espías, Alicia y Bob pueden comparar sobre el canal público determinadas posiciones, aleatoriamente elegidas de sus claves brutas. Si las no coincidencias superan una cota prefijada, abortan el protocolo y empiezan de nuevo.

Por ejemplo, si quieren una clave de longitud n, pueden llevan a cabo el protocolo para obtener como clave bruta una cadena de longitud 2n, de los que usan n para chequear los errores. Si tras el chequeo de n bits no hallan discrepancias (o están por debajo de la cota prefijada), pueden suponer que no ha habido espías y quedarse con los otros n bits como clave depurada, que posteriormente será sometida a procesos de corrección de errores y amplificación de la privacidad, para obtener la clave secreta final.

Cuestiones para reflexionar e investigar:
Busca información sobre protocolos de Amplificación de la privacidad y estudia cómo se puede aplicar a la clave depurada de Alicia y Bob, usando el canal clásico de comunicación y en qué medida se reducirá el tamaño de la clave.

El protocolo BB84 se puede llevar a cabo con la tecnología actual usando fotones polarizados enviados a través de fibra óptica. De hecho hay empresas como IDQ o MagiQ que comercializan sistemas que permiten llevar a cabo protocolos de QKD.

img/L2_F9.jpg img/L2_F9b.jpg

Dispositivos para protocolos de QKD


APARTADO 2.3. SEGURIDAD DEL PROTOCOLO BB84

La seguridad de los protocolos cuánticos de distribución de claves se basa en que los comunicantes legítimos pueden detectar la presencia de un espía porque, al medir los estados cuánticos, éste introduce discrepancias en la clave. Así, pueden chequear un trozo de la clave generada y rechazarla, en caso de encontrar discrepancias. img/L2_Eva.jpg

Pero, en un sistema práctico de distribución cuántica de claves, pueden aparecer errores, debidos a imperfecciones técnicas del emisor o del receptor, o simplemente a cambios de temperatura, y no a la presencia de un espía. Por ello es importante determinar una cota de errores admisibles por encima de la cual se debe abortar el proceso y para ello es necesario analizar los efectos de las posibles estrategias de espionaje sobre el protocolo a utilizar.

Cuando la tasa de error está por debajo de la cota, se admitirá la clave generada y se llevará a cabo un proceso de depuración en el que los errores se pueden detectar y corregir con códigos clásicos usando el canal clásico de comunicación.

Estrategias de ataque individual al protocolo BB84

En un modelo ideal, la fuente emite fotones individuales y Eva ataca de modo independiente cada qubit.
Como primera opción, vamos a suponer que Eva ha espiado la comunicación y que actúaa del siguiente modo:
Intercepta el fotón enviado por Alicia, elige aleatoriamente una de las dos bases B1 o BX, mide el qubit recibido, guarda el resultado de la medición y envía a Bob el qubit resultante. Tras la fase de reconciliación de bases Eva se queda solo con los bits correspondientes a las posiciones en las que Alicia y Bob han usado la misma base.
img/L2_F10.jpg

Esta estrategia de ataque individual se denomina Interceptar-Reenviar.

Alicia y Bob pueden detectar la presencia de Eva, ya que su actuación cambia el estado de algunos de los qubits que envía a Bob. Para hacer el estudio de la seguridad del protocolo BB84 analizaremos las probabilidades sobre cada bit de la clave. Denominamos discrepancia y denotamos por d, a la probabilidad de que un bit de la clave de Bob no coincida con el correspondiente de Alicia. Alicia y Bob van a utilizar una parte de sus claves para estimar la discrepancia y han de decidir previamente una cota admisible por debajo de la cual consideran que el protocolo es seguro y que los errores son debidos a ruidos o interferencias y no a la presencia de espías.

Ejercicio 2.2.2
Completa la siguiente tabla (que puedes descargarte aquí). En ella se muestra un ejemplo en el que Eva sigue una estrategia de espionaje Interceptar-Reenviar. Rellénala varias veces poniendo posibles resultados diferentes en las medidas y en cada caso contesta a las siguiente preguntas:
¿Cuántos bits tiene la clave tras la reconciliación de bases?
¿Para cuántos de estos bits son coincidentes las cadenas de Alicia y Eva?
¿Qué discrepancia ha introducido Eva en la clave de Bob?

img/L2_F18.jpg

Efecto de la estrategia Interceptar-Reenviar:

Tras la fase de reconciliación de bases. Alicia, Bob y Eva tienen cadenas del bits del mismo tamaño.

Vamos a calcular la probabilidad de acierto de cada bit de la cadena de Eva:

Sea a el bit de Alicia, a" el de Bob y B la base usada por ambos. Denominamos B' la base elegida por Eva y a' el bit resultante tras su medición. Entonces la probabilidad de coincidencia entre los bits de Alicia y Eva es:

P(a=a')=P(a=a'/B=B')P(B=B')+ P(a=a'/B≠B')P(B≠B')=1·0.5+0.5·0.5 = 0.75

Para ver cómo la actuación de Eva ha afectado a la clave de Bob, vamos ahora a calcular la probabilidad de coincidencia de los bits de Alicia y Bob:

P(a=a")= P(a=a''/B=B')P(B=B')+P(a=a''/B≠B')P(B≠B')= 1·0.5 + 0.5·0.5 = 0.75

De los resultados anteriores se obtiene la siguiente consecuencia: Con la estrategia Interceptar-Reenviar, la cadena de Eva tendrá el 75% de aciertos y la discrepancia introducida en la clave de Bob será del 25%.

Otras estrategias de espionaje

Eva puede usar otras estrategias, con el objetivo de aumentar su probabilidad de acierto y/o disminuir la discrepancia introducida en la clave de Bob. Por ejemplo, en lugar de elegir aleatoriamente la base, puede medir siempre con una base que le maximice la probabilidad de acierto.

img/L2_F11.jpg

Ejercicio 2.2.3
Demuestra que con la estrategia de la base intermedia la máxima probabilidad de acierto se alcanza con α=π/8. Calcula en ese caso, la probabilidad de acierto y la discrepancia introducida

Ante diferentes estrategias de espionaje, parece razonable considerar mejor aquélla que permita a Eva obtener mayor probabilidad de acierto y menor discrepancia. Diremos que una estrategia de espionaje es óptima si maximiza el valor de p+f, donde p es la probabilidad de acierto de Eva y f=1-d es la fidelidad de la clave de Bob.

Con esta idea, la estrategia de la base intermedia es mejor que la de Interceptar-Reenviar. Se puede comprobar que para la primera es p+f tiene un valor aproximado 1.603, mientras que para la segunda este valor es p+f=1.5.

Pero, además de las consideradas, Eva puede llevar a cabo otras estrategias, ya que puede hacer con los qubits interceptados cualquier manipulación que no viole las leyes de la mecánica cuántica. Con la hipótesis de ataque individual, podemos establecer, para el protocolo BB84, una estrategia general de espionaje en los siguientes términos:

  • 1. Eva intercepta el qubit |x> emitido por Alicia.
  • 2. Añade un n-qubit de prueba en estado |0> y le aplica una transformación unitaria arbitraria T.
  • 3. Envía a Bob el primer qubit de dicho estado.
  • 4. Espera a la reconciliación de bases y mide uno de sus qubits para obtener su clave.

Para establecer una cota de discrepancia admisible, que garantice la seguridad del protocolo, hay que investigar la relación entre la discrepancia introducida y la probabilidad de acierto en una estrategia general. Pero no siempre la forma más adecuada de valorar la información del espía es mediante el número estimado de bits coincidentes de su clave. Por ejemplo, hemos visto que con la estrategia de la base intermedia, Eva consigue mayor probabilidad de acierto que si utiliza aleatoriamente B1 o BX, sin introducir más discrepancia. Pero pierde la información relativa a las posiciones correctas de su clave, que conocería tras la reconciliación de bases si hubiera utilizando B1 o BX.

Medida de la información

Hay distintas formas de medir la información que tiene el espía y la estrategia óptima de espionaje dependerá de la forma que se adopte para medir la información. A continuación vamos a introducir algunos conceptos relacionados con las formas de medir la información.

Dada una variable aleatoria discreta X que puede tomar valores X1,X2,..,Xn, con distribución de probabilidad p1,p2,..,pn, se define la entropía de Shannon del siguiente modo:

img/L2_F12.jpg

Si X e Y son dos variables aleatorias se puede hablar de entropía conjunta, H(X,Y), y de entropía condicionada, H(X|Y), correspondientes a las distribuciones de probabilidad conjunta y condicionada, respectivamente. Se verifica que H(X|Y)=H(X,Y)-H(Y) y que H(X,Y) ≤ H(X)+ H(Y), con igualdad si y solo si las variables aleatorias son independientes.

La información mutua entre las variables X e Y se define como: I(X,Y)=H(X)+H(Y)-H(X,Y)=H(X)-H(X|Y)

Obviamente I(X,Y)=I(Y,X) lo que justifica el adjetivo "mutua".

La información mutua siempre es mayor o igual que 0 y será 0 si las variables son independientes (una de ellas no proporciona ninguna información sobre la otra). La información mutua mide la diferencia de incertidumbres sobre X antes y después de conocer Y. El hecho de que I(X,Y) sea pequeña indica que el conocimiento de Y aporta muy poca información sobre X.

img/L2_F13.jpg

Imponiendo que la información mutua entre Alicia y Bob sea mayor que la información mutua entre Alicia y Eva, se obtiene que el protocolo BB84 es seguro frente a ataques individuales cuando la tasa de discrepancias está por debajo del 11%. Con ese porcentaje de discrepancia, los protocolos de amplificación de privacidad permiten garantizar la seguridad total de la clave secreta final.

Limitaciones de seguridad del BB84

Desde un punto de vista práctico, los experimentos basados en pulsos débilmente coherentes han puesto de manifiesto ciertas limitaciones de seguridad que no aparecen en los esquemas idealizados. Está admitida la seguridad del protocolo BB84 si se supone que Alicia dispone de un emisor capaz de emitir fotones individuales, pero en la práctica la probabilidad de multifotón es apreciable. Ya en el año 2000 se demostró experimentalmente que la distribución cuántica de clave, usando fibra óptica, es factible (ver [1]). Pero en el experimento se comprobó que el 28% de los pulsos láser detectables que salieron del interferómetro de Alicia contenían dos o más fotones. Habría que contemplar por lo tanto la posibilidad de que Eva realice un ataque de los denominados PNS (Photon Number Splitting) basado en pulsos con dos fotones, consistente es escindir los dos fotones del pulso, enviar a Bob uno de ellos y almacenar el otro en una memoria cuántica, esperar a la reconciliación de bases y medir su fotón con la base adecuada.

Un análisis riguroso de la seguridad, que contemple no sólo las posibilidades de la tecnología actual sino también las de la previsible tecnología futura es tarea pendiente. Sin embargo, completando los protocolos de QKD con procesos de corrección de errores y amplificación de la privacidad, se puede garantizar la seguridad de las claves distribuidas [5].


APARTADO 2.4. OTROS PROTOCOLOS CUÁNTICOS DE DISTRIBUCIÓN DE CLAVES

Veremos en este apartado tres protocolos de QKD.

2.4.1. Protocolo B92

El protocolo B92 [2], propuesto por Bennet en 1992, es una generalización muy simple del BB84, que utiliza solamente dos estados no ortogonales.

img/L2_F14.jpg

Ejercicio 2.4.1
Pon un ejemplo del protocolo B92, con una cadena de al menos 12 bits.

2.4.2 Protocolo SARG04

El protocolo SARG04 [7], propuesto por Scarini, Acín, Ribordy y Gisin en 2004, es una generalización del BB84, más robusto frente a ataques PNS.

img/L2_F15.jpg img/L2_F16.jpg

Cuestiones para reflexionar e investigar:
¿Por qué el protocolo SARG04 es robusto frente a ataques PNS?

2.4.3 Protocolo E91

El protocolo E91 [4], propuesto por A. Ekert en 1991, basa su seguridad en el uso de pares EPR. Un par EPR es un estado cuántico de 2 qubits entrelazados.

La idea consiste en reemplazar el canal cuántico usado para enviar qubits de Alicia a Bob por un emisor que envía el primer qubit de un par EPR a Alicia y el segundo a Bob. Una vez que Alicia y Bob comparten un conjunto de pares EPR, seleccionan aleatoriamente una parte de ellos, para comprobar su grado de correlación que teóricamente debe ser perfecta. Si es así, tienen garantizado que los restantes son estados cuánticos entrelazados y realizan con ellos el protocolo.

img/L2_F17.jpg

APARTADO 2.5. TEST DE AUTOEVALUACIÓN



1. La principal aportación de la mecánica cuántica a la criptografía es:
a) La posibilidad de usar computación cuántica para acelerar los procesos de cifrado o descifrado.
b) La posibilidad de distribuir claves privadas de las que un espía no puede obtener información sin alterarlas.
c) La posibilidad de unir un proceso de cifrado simétrico con un asimétrico.

2. Si no ha habido espías ni interferencias en el protocolo BB84, antes de la fase de reconciliación de bases, las cadenas de bits Alicia y Bob son coincidentes aproximadamente en un:
a) 75%
b) 50%
c) 25%

3. La clave bruta y la clave depurada del protocolo BB84:
a) Tienen que ser exactamente iguales.
b) Pueden tener alguna discrepancia.
c) La clave depurada es una parte de la clave bruta.

4. En el protocolo B92, se utiliza para codificar
a) Dos estados cuánticos ortogonales.
b) Dos estados cuánticos no ortogonales.
c) Dos estados cuánticos cualesquiera.

5. ¿Cuál de los siguientes protocolos cuánticos de distribución de claves tiene más dificultades técnicas de implementación?
a) El BB84.
b) El SARG04.
c) El E91.

Consultar soluciones razonadas

APARTADO 2.6. REFERENCIAS BIBLIOGRÁFICAS Y ENLACES DE INTERÉS

[1] Brassard, G. Lütkenhaus, N. , Mor, T. and Sloane, N.J. Limitations of Practical Quantum Cryptography. Phys. Rev. Lett. 85, pp. 1330-1333 (2000).

[2] Bennet, C.H. Quantum Cryptography using any two nonorthogonal states, Phys. Rev. Lett. 68, pp. 3121-3124 (1992).

[3] Bennet, C.H, Brassard, G. Quantum Cryptography: public key distribution and coin tossing. Proc of IEEE Int. Conf. on Computers, Systems and Signal Preocessing, pp.175-179 (1984).

[4] Ekert, A. Quantum Cryptography based on Bell's theorem. Phys. Rev. Lett. 67, pp. 661-663 (1991).

[5] Gottesman D. , Lo, H.K. N. Lutkenhaus, and J. Preskill, J. Security of Quantum Key Distribution with Imperfect Devices, Quant. Inf. Comp. 4, PP.325-360 (2004).

[6] Nielsen, M. A.; Chuang, L. I., Quantum Computation and Quantum Information, Cambridge University Press, 2000.

[7] Scarani, V., Acín, A., Ribordy, G. and Gisin, N. Quantum Cryptography Protocols Robust against Photon Number Splitting Attacks for Weak Laser Pulse Implementations, Phys. Rev. Lett. 92, 057901 (2004)

[8] http://www.csee.umbc.edu/~lomonaco/ams/lecturenotes/SamCrypto.pdf


Ir a: [Principio]