Lanzamiento de moneda cuántica

Consideremos dos jugadores remotos, conectados por un canal, que no confían entre sí. El problema de que se pongan de acuerdo sobre un bit aleatorio intercambiando mensajes a través de este canal, sin depender de ningún tercero de confianza, se denomina problema de lanzamiento de moneda en criptografía. ^[1] El lanzamiento de moneda cuántico utiliza los principios de la mecánica cuántica para cifrar mensajes para una comunicación segura. Es un primitivo criptográfico que se puede utilizar para construir protocolos criptográficos más complejos y útiles, ^[2] por ejemplo, el acuerdo bizantino cuántico .

A diferencia de otros tipos de criptografía cuántica (en particular, la distribución de claves cuánticas ), el lanzamiento de moneda cuántica es un protocolo utilizado entre dos usuarios que no confían entre sí. ^[3] En consecuencia, ambos usuarios (o jugadores) quieren ganar el lanzamiento de moneda e intentarán hacer trampa de diversas formas. ^[3]

En el contexto clásico, es decir, sin comunicación cuántica, un jugador puede (en principio) siempre hacer trampas contra cualquier protocolo. ^[4] Existen protocolos clásicos basados ​​en esquemas de compromiso , pero suponen que los jugadores carecen de la potencia informática necesaria para romper el esquema. Por el contrario, los protocolos de lanzamiento de moneda cuántico pueden resistir las trampas incluso por parte de jugadores con potencia informática ilimitada.

La cifra de mérito más básica para un protocolo de lanzamiento de moneda está dada por su sesgo, un número entre y . El sesgo de un protocolo captura la probabilidad de éxito de un jugador tramposo todopoderoso que utiliza la mejor estrategia concebible. Un protocolo con sesgo significa que ningún jugador puede hacer trampa. Un protocolo con sesgo significa que al menos un jugador siempre puede tener éxito en hacer trampa. Obviamente, cuanto menor sea el sesgo, mejor será el protocolo. ${\displaystyle 0}$ ${\displaystyle 1/2}$ ${\displaystyle 0}$ ${\displaystyle 1/2}$

Cuando la comunicación se realiza a través de un canal cuántico , se ha demostrado que incluso el mejor protocolo concebible no puede tener un sesgo menor a . ^{[5] [6]} ${\displaystyle 1/{\sqrt {2}}-1/2\approx 0.2071}$

Consideremos el caso en el que cada jugador conoce el bit preferido del otro. Un problema de lanzamiento de moneda que hace esta suposición adicional constituye la variante más débil del mismo, llamada lanzamiento de moneda débil (WCF). En el caso de los canales clásicos, esta suposición adicional no produce ninguna mejora. Por otro lado, se ha demostrado que existen protocolos WCF con sesgos arbitrariamente pequeños. ^{[7] [8]} Sin embargo, el protocolo WCF explícito más conocido tiene sesgo . ^[9] ${\displaystyle 1/6\approx 0.1667}$

Aunque el lanzamiento de monedas cuántico ofrece claras ventajas sobre su contraparte clásica en teoría, lograrlo en la práctica ha resultado difícil. ^{[3] [10]}

Historia

Teoría

Manuel Blum introdujo el lanzamiento de monedas como parte de un sistema clásico en 1983 basado en algoritmos computacionales y suposiciones. ^[11] La versión de Blum del lanzamiento de monedas responde al siguiente problema criptográfico:

Alice y Bob se divorciaron recientemente, viven en dos ciudades diferentes y quieren decidir quién se queda con el auto. Para decidir, Alice quiere lanzar una moneda por teléfono. Sin embargo, a Bob le preocupa que si le dice a Alice que sale cara, ella lanzará la moneda y automáticamente le dirá que perdió. ^[12]

Así, el problema con Alice y Bob es que no confían el uno en el otro; el único recurso que tienen es el canal de comunicación telefónica y no hay un tercero disponible para leer la moneda. Por lo tanto, Alice y Bob deben ser sinceros y estar de acuerdo sobre un valor o estar convencidos de que el otro está haciendo trampa. ^[12]

En 1984, la criptografía cuántica surgió a partir de un artículo escrito por Charles H. Bennett y Giles Brassard. En este artículo, ambos introdujeron la idea de utilizar la mecánica cuántica para mejorar los protocolos criptográficos anteriores, como el lanzamiento de una moneda. ^[3] Desde entonces, muchos investigadores han aplicado la mecánica cuántica a la criptografía, ya que han demostrado ser teóricamente más seguros que la criptografía clásica; sin embargo, demostrar estos protocolos en sistemas prácticos es difícil de lograr.

Experimento

Como se publicó en 2014, un grupo de científicos del Laboratorio de Comunicación y Procesamiento de Información (LTCI) de París ha implementado experimentalmente protocolos de lanzamiento de monedas cuánticas. ^[3] Los investigadores han informado que el protocolo funciona mejor que un sistema clásico en una distancia adecuada para una red óptica de área metropolitana. ^[3]

Definición

Lanzamiento de moneda

En criptografía, el lanzamiento de una moneda se define como el problema en el que dos jugadores mutuamente desconfiados y remotos quieren ponerse de acuerdo sobre un bit aleatorio sin depender de ningún tercero. ^[1]

Fuerte lanzamiento de moneda

En criptografía cuántica, el lanzamiento fuerte de moneda (SCF) se define como un problema de lanzamiento de moneda en el que cada jugador no tiene en cuenta las preferencias del otro. ^[13]

Lanzamiento de moneda débil

En criptografía cuántica, el lanzamiento de moneda débil (WCF) se define como un problema de lanzamiento de moneda en el que cada jugador conoce la preferencia del otro. ^[14]

De ello se deduce que los jugadores tienen preferencias opuestas. Si no fuera así, el problema no tendría sentido, ya que los jugadores podrían simplemente elegir el resultado que deseen.

Inclinación

Consideremos cualquier protocolo de lanzamiento de moneda. Sean Alice y Bob los dos jugadores que desean implementar el protocolo. Consideremos el escenario en el que Alice hace trampa usando su mejor estrategia contra Bob, quien honestamente sigue el protocolo. Sea la probabilidad de que Bob obtenga el resultado que Alice prefería dada por . Consideremos la situación inversa, es decir, Bob hace trampa usando su mejor estrategia contra Alice, quien honestamente sigue el protocolo. Sea la probabilidad correspondiente de que Alice obtenga el resultado que Bob prefería dada por . ${\displaystyle P_{A}^{*}}$ ${\displaystyle P_{B}^{*}}$

El sesgo del protocolo se define como . ${\textstyle \epsilon :=\max[P_{A}^{*},P_{B}^{*}]-{\frac {1}{2}}}$

Se resta la mitad porque un jugador obtendrá el valor deseado la mitad de las veces por pura casualidad.

Extensiones

El lanzamiento de moneda también se puede definir para monedas sesgadas, es decir, los bits no tienen la misma probabilidad. También se ha formalizado el concepto de corrección, que exige que cuando ambos jugadores siguen el protocolo (nadie hace trampas), los jugadores siempre están de acuerdo en el bit generado y que este sigue una distribución de probabilidad fija.

Protocolos

Usando codificación conjugada

El lanzamiento de monedas cuánticas y otros tipos de criptografía cuántica comunican información mediante la transmisión de cúbits . El jugador que acepta no conoce la información contenida en el cúbit hasta que realiza una medición. ^[12] La información sobre cada cúbit se almacena y transporta en un único fotón . ^[10] Una vez que el jugador receptor mide el fotón, este se altera y no producirá el mismo resultado si se vuelve a medir. ^[10] Dado que un fotón solo se puede leer de la misma manera una vez, cualquier otra parte que intente interceptar el mensaje es fácilmente detectable. ^[10]

El lanzamiento de moneda cuántico se produce cuando se generan cúbits aleatorios entre dos jugadores que no confían entre sí porque ambos quieren ganar el lanzamiento de moneda, lo que podría llevarlos a hacer trampa de diversas maneras. ^[3] La esencia del lanzamiento de moneda ocurre cuando los dos jugadores emiten una secuencia de instrucciones a través de un canal de comunicación que luego eventualmente da como resultado un resultado. ^[10]

Un protocolo básico de lanzamiento de moneda cuántica involucra a dos personas: Alice y Bob. ^[11]

1. Alice envía a Bob una cantidad determinada de pulsos de fotones Κ en los estados cuánticos . Cada uno de estos pulsos de fotones se prepara de forma independiente siguiendo una elección aleatoria por parte de Alice de la base α _i y el bit c _i donde i = 1, 2, 3...Κ. ${\displaystyle |\phi _{\alpha _{i}c_{i}}\rangle }$
2. Luego, Bob mide los pulsos de Alice identificando una base aleatoria β _i . Bob registra estos fotones y luego informa a Alice el primer fotón j medido con éxito junto con un bit aleatorio b .
3. Alice revela la base y el bit que utilizó en la base que le dio Bob. Si las dos bases y los bits coinciden, entonces ambas partes son veraces y pueden intercambiar información. Si el bit informado por Bob es diferente al de Alice, uno no está siendo veraz.

Alice decide su base aleatoria y la secuencia de qubits. Luego envía los qubits como fotones a Bob a través del canal cuántico. Bob detecta estos qubits y registra sus resultados en una tabla. Basándose en la tabla, Bob le hace una suposición a Alice sobre qué base utilizó.

Una explicación más general del protocolo anterior es la siguiente: ^[15]

1. Alice elige primero una base aleatoria (por ejemplo, en diagonal) y una secuencia de cúbits aleatorios. Luego, Alice codifica los cúbits elegidos como una secuencia de fotones que siguen la base elegida. Luego, envía estos cúbits como un tren de fotones polarizados a Bob a través del canal de comunicación.
2. Bob elige una secuencia de bases de lectura al azar para cada fotón individual. Luego lee los fotones y registra los resultados en dos tablas. Una tabla es de los fotones recibidos en línea recta (horizontal o vertical) y otra de los fotones recibidos en diagonal. Bob puede tener lagunas en sus tablas debido a pérdidas en sus detectores o en los canales de transmisión. Bob ahora intenta adivinar qué base utilizó Alice y anuncia su suposición a Alice. Si adivinó correctamente, gana y si no, pierde.
3. Alice le informa a Bob si ganó o no anunciando qué base utilizó. Luego, Alice confirma la información enviándole a Bob toda la secuencia de cúbits original que utilizó en el paso 1.
4. Bob compara la secuencia de Alice con sus tablas para confirmar que Alice no hizo trampa. Las tablas deberían corresponder a la base de Alice y no debería haber correlación con la otra tabla.

Supuestos

Hay algunas suposiciones que deben hacerse para que este protocolo funcione correctamente. La primera es que Alice puede crear cada estado independientemente de Bob y con una probabilidad igual. En segundo lugar, para el primer bit que Bob mide con éxito, su base y bit son aleatorios y completamente independientes de Alice. La última suposición es que cuando Bob mide un estado, tiene una probabilidad uniforme de medir cada estado y ningún estado es más fácil de detectar que otros. Esta última suposición es especialmente importante porque si Alice fuera consciente de la incapacidad de Bob para medir ciertos estados, podría usar eso a su favor. ^[11]

Infiel

El problema clave con el lanzamiento de una moneda es que se produce entre dos partes que desconfían. ^[15] Estas dos partes se comunican a través del canal de comunicación a cierta distancia una de la otra y tienen que ponerse de acuerdo sobre un ganador o un perdedor, teniendo cada uno un 50 por ciento de posibilidades de ganar. ^[15] Sin embargo, como desconfían una de la otra, es probable que se produzcan trampas. Las trampas pueden ocurrir de varias maneras, como afirmar que perdieron parte del mensaje cuando no les gusta el resultado o aumentar el número promedio de fotones contenidos en cada uno de los pulsos. ^[3]

Para que Bob haga trampa, tendría que poder adivinar la base de Alice con una probabilidad mayor que ⁠1/2⁠ . ^[15] Para lograr esto, Bob tendría que ser capaz de determinar un tren de fotones polarizados aleatoriamente en una base a partir de un tren de fotones polarizados en otra base. ^[15]

Alice, por otro lado, podría hacer trampa de varias maneras diferentes, pero tiene que tener cuidado porque Bob podría detectarlo fácilmente. ^[15] Cuando Bob envía una suposición correcta a Alice, ella podría convencer a Bob de que sus fotones están polarizados en realidad de manera opuesta a la suposición correcta de Bob. ^[15] Alice también podría enviar a Bob una secuencia original diferente a la que realmente utilizó para vencer a Bob. ^[15]

Detección de un tercero

Se utilizan fotones individuales para pasar la información de un jugador a otro (qubits). ^[10] En este protocolo, la información se codifica en fotones individuales con direcciones de polarización de 0, 45, 90 y 135 grados, estados cuánticos no ortogonales. ^[15] Cuando un tercero intenta leer u obtener información sobre la transmisión, altera la polarización del fotón de una manera aleatoria que probablemente sea detectada por los dos jugadores porque no coincide con el patrón intercambiado entre los dos usuarios legítimos. ^[15]

El protocolo Dip Dip Boom (lanzamiento de moneda débil con sesgo) 1 / 6 {\textstyle 1/6} )

El protocolo Dip Dip Boom (DDB) es una versión cuántica del siguiente juego. ^[9] Considere una lista de números , cada uno entre 0 y 1. Los jugadores, Alice y Bob, se turnan para decir "Dip" o "Boom" con probabilidad en la ronda . El jugador que dice "Boom" gana. Obviamente, un jugador tramposo puede simplemente decir "Boom" y ganar, ya que no hay recompensas para juegos más largos. Consideraremos juegos que terminan de modo que para algún (grande) , digamos , establezcamos . ${\displaystyle {p_{i}}}$ ${\displaystyle p_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle p_{i}=1}$

Consideremos la ronda . Denotemos por y la probabilidad de que Alice y Bob ganen, respectivamente. Sea la probabilidad de que el juego permanezca indeciso. Estos números para el juego clásico descrito anteriormente se pueden evaluar de forma inductiva. ${\displaystyle i}$ ${\displaystyle P_{A}(i)}$ ${\displaystyle P_{B}(i)}$ ${\displaystyle P_{U}(i)}$

Ahora describimos la versión cuántica. Sea un espacio de Hilbert tridimensional abarcado por . Sea un espacio de Hilbert bidimensional abarcado por . ${\displaystyle {\mathcal {A}},{\mathcal {B}}}$ ${\displaystyle |A\rangle ,|B\rangle ,|U\rangle }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle |{\text{DIP}}\rangle ,|{\text{BOOM}}\rangle }$

1. Inicialización : Alice conserva los registros e inicializa el estado en . Bob conserva el registro y lo inicializa en el estado . ${\displaystyle {\mathcal {A}}\otimes {\mathcal {M}}}$ ${\displaystyle |U\rangle \otimes |{\text{DIP}}\rangle }$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle |U\rangle }$
2. Iteración : Para los números impares, se debe realizar lo siguiente: para los números pares, se establece X=A (para Alice) e Y=B (para Bob); para los números pares, se establece X=B e Y=A. ${\displaystyle i=1}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle i}$
   • X implementa la operación . ${\displaystyle R_{i}:={\text{Rot}}(|U\rangle \otimes |{\text{DIP}}\rangle ,|X\rangle \otimes |{\text{BOOM}}\rangle ,p_{i})}$
   • X envía el registro de mensajes a Y.
   • Y implementa la operación . ${\displaystyle {\tilde {R}}_{i}:={\text{Rot}}\left(|U\rangle \otimes |{\text{BOOM}}\rangle ,|X\rangle \otimes |{\text{DIP}}\rangle ,{\frac {p_{i}P_{U}(i-1)}{P_{X}(i)}}\right)}$
   • Y mide el registro de mensajes en la base computacional. Si el resultado es BOOM, Y cancela la operación y se declara ganador.
3. Medición : Alice y Bob miden sus registros locales y respectivamente. Si el resultado es U, se declaran ganadores. Si el resultado es A, Alice es la ganadora y, en el caso de B, Bob es el ganador. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

Observaciones

• Para obtener un protocolo equilibrado se deben elegir los s tales que . ${\displaystyle p_{i}}$ ${\displaystyle P_{A}(n)={\frac {1}{2}}=P_{B}(n)}$
• Si ambos jugadores siguen el protocolo, es decir, ningún jugador hace trampa, entonces el resultado al final del paso dos nunca será BOOM y el resultado en el paso 3 tampoco lo será . ${\displaystyle |U\rangle }$
• El análisis de sesgo de este protocolo utiliza la dualidad SDP .
• Para tamaños grandes, el sesgo del protocolo se puede hacer arbitrariamente cercano a . ${\displaystyle n}$ ${\displaystyle 1/6}$

Lanzamiento de moneda fuerte óptimo

Se ha demostrado que utilizando un protocolo WCF con un sesgo arbitrariamente pequeño se puede construir un protocolo SCF con un sesgo arbitrariamente cercano al que se sabe que es óptimo. ^[16] ${\textstyle {\frac {1}{\sqrt {2}}}-{\frac {1}{2}}}$

Implementación experimental

Usando codificación conjugada

Como se mencionó en la sección de historia, los científicos del LTCI en París han llevado a cabo experimentalmente un protocolo de lanzamiento de moneda cuántico. Los protocolos anteriores requerían una única fuente de fotones o una fuente entrelazada para ser segura. Sin embargo, estas fuentes son la razón por la que es difícil implementar el lanzamiento de moneda cuántico. En cambio, los investigadores del LTCI utilizaron los efectos de la superposición cuántica en lugar de una única fuente de fotones, lo que, según afirman, hace que la implementación sea más fácil con las fuentes de fotones estándar disponibles. ^[3]

Los investigadores utilizaron la plataforma Clavis2 desarrollada por IdQuantique para su protocolo, pero tuvieron que modificar el sistema Clavis2 para que funcionara con el protocolo de lanzamiento de moneda. La configuración experimental que utilizaron con el sistema Clavis2 implica un enfoque bidireccional. Bob envía pulsos de luz a 1550 nanómetros a Alice. Luego, Alice utiliza un modulador de fase para cifrar la información. Después del cifrado, utiliza un espejo de Faraday para reflejar y atenuar los pulsos en el nivel elegido y los envía de vuelta a Bob. Utilizando dos detectores de fotones individuales de alta calidad, Bob elige una base de medición en su modulador de fase para detectar los pulsos de Alice. ^[11]

Reemplazaron los detectores del lado de Bob debido a la baja eficiencia de detección de los detectores anteriores. Cuando reemplazaron los detectores, pudieron demostrar una ventaja cuántica en un canal de más de 15 kilómetros (9,3 millas). Un par de desafíos más que enfrentó el grupo fue reprogramar el sistema debido a que la atenuación de la fuente de fotones era alta y realizar análisis del sistema para identificar pérdidas y errores en los componentes del sistema. Con estas correcciones, los científicos pudieron implementar un protocolo de lanzamiento de moneda introduciendo una pequeña probabilidad de aborto honesto, la probabilidad de que dos participantes honestos no puedan obtener un lanzamiento de moneda al final del protocolo, pero a una corta distancia de comunicación. ^[3]

Referencias

1. Blum, Manuel (1983-01-01). "Lanzar una moneda por teléfono: un protocolo para resolver problemas imposibles". ACM SIGACT News . 15 (1): 23–27. doi : 10.1145/1008908.1008911 . ISSN  0163-5700. S2CID  19928725.
2. Oded., Goldreich (2003). Fundamentos de la criptografía . Cambridge, Reino Unido: Cambridge University Press. ISBN 9780521791724.OCLC 45093786  .
3. Stuart Mason Dambort, "Cara o cruz: la criptografía experimental de lanzamiento de monedas cuántica funciona mejor que los protocolos clásicos", Phys.org , 26 de marzo de 2014
4. Cleve, R. (1986-11-01). "Límites a la seguridad de los lanzamientos de moneda cuando la mitad de los procesadores son defectuosos". Actas del decimoctavo simposio anual de la ACM sobre teoría de la computación - STOC '86 . ACM. págs. 364–369. doi :10.1145/12130.12168. ISBN 0897911938.S2CID 17394663  .
5. A. Kitaev, Lanzamiento cuántico de monedas, Taller de procesamiento de información cuántica, Instituto de Investigación en Ciencias Matemáticas, Universidad de California, Berkeley, 2003.
6. Ambainis, A.; Buhrman, H.; Dodis, Y.; Rohrig, H. (2004). "Lanzamiento de moneda cuántica multipartidista". Actas. 19.ª Conferencia anual del IEEE sobre complejidad computacional, 2004. IEEE. págs. 250–259. arXiv : quant-ph/0304112 . doi :10.1109/ccc.2004.1313848. ISBN . 0769521207. Número de identificación del sujeto  3261413.
7. C. Mochon, Lanzamiento cuántico de moneda débil con sesgo arbitrariamente pequeño, preimpresión, arXiv:0711.4114, 2007.
8. Aharonov, Dorit; Chailloux, André; Ganz, maorí; Kerenidis, Iordanis; Magnin, Loïck (enero de 2016). "Una prueba más simple de la existencia del lanzamiento de monedas cuánticas débiles con un sesgo arbitrariamente pequeño". Revista SIAM de Computación . 45 (3): 633–679. arXiv : 1402.7166 . doi :10.1137/14096387x. ISSN  0097-5397. S2CID  7519640.
9. Mochon, Carlos (2005). "Gran familia de protocolos cuánticos de lanzamiento de moneda débil". Physical Review A . 72 (2): 022341. arXiv : quant-ph/0502068 . Código Bibliográfico :2005PhRvA..72b2341M. doi :10.1103/PhysRevA.72.022341. S2CID  46533337.
10. Vivek R y Dr. J. Roopchand, "Tendencias emergentes en criptografía cuántica: una encuesta", Revista internacional de tecnología informática y aplicaciones , agosto de 2012
11. Anna Pappa et al., "Lanzamiento de una moneda cuántica experimental, plug and play", Nature Communications , 24 de abril de 2014
12. C. Döscher y M. Keyl, "Introducción al lanzamiento de monedas cuántico", Biblioteca de la Universidad de Cornell , 1 de febrero de 2008
13. D. Aharonov, A. Ta-Shma, UV Vazirani y AC Yao, Quantum bit escrow, en Actas del 32º Simposio Anual de la ACM sobre Teoría de la Computación, ACM, Nueva York, 2000, págs. 705–714.
14. Spekkens, RW (2002). "Protocolo cuántico para lanzamiento de moneda débil sensible a trampas". Physical Review Letters . 89 (22): 227901. arXiv : quant-ph/0202118 . Código Bibliográfico :2002PhRvL..89v7901S. doi :10.1103/PhysRevLett.89.227901. PMID  12485105. S2CID  42694366.
15. Charles H. Bennett y Giles Brassard, "Criptografía cuántica: distribución de claves públicas y lanzamiento de moneda", Theoretical Computer Science , 4 de diciembre de 2014
16. 50.° Simposio anual IEEE sobre fundamentos de la informática, FOCS '09 2009; 25-27 de octubre de 2009, Atlanta, Georgia, EE. UU.; actas . Comité técnico de la IEEE Computer Society sobre fundamentos matemáticos de la informática, Simposio anual IEEE sobre fundamentos de la informática 50 25-27 de octubre de 2009 Atlanta, Georgia, FOCS 50 25-27 de octubre de 2009 Atlanta, Georgia. Piscataway, NJ. 2009. ISBN 9781424451166.OCLC 838170374  .{{cite book}}: CS1 maint: falta la ubicación del editor ( enlace ) CS1 maint: otros ( enlace )