Malleability of transformations on the ciphertext in noisy Quantum public key encryption

Resumen Técnico: Maleabilidad de las Transformaciones sobre el Cifrado en la Criptografía de Clave Pública Cuántica con Ruido

Planteamiento del Problema
Este artículo aborda el desafío de formular rigurosamente la "seguridad eterna" (everlasting security) para la Criptografía de Clave Pública Cuántica (QPKE) y la Distribución de Claves Cuánticas (QKD) en presencia de ruido. Mientras que el trabajo previo de Malavolta y Walter [3] estableció un marco para la seguridad eterna en un entorno sin ruido —demostrando que la seguridad puede lograrse tras solo dos rondas de interacción entre Alice y Bob—, este trabajo investiga cómo la introducción de ruido afecta los umbrales de seguridad del protocolo. Específicamente, el artículo explora la relación entre la maleabilidad de las transformaciones del texto cifrado y la seguridad del protocolo cuando se inyecta ruido en las operaciones criptográficas. El problema central es generalizar la función de negligibilidad (que cuantifica la ventaja del adversario) desde el caso ideal sin ruido hacia un entorno con ruido, utilizando supuestos sobre la maleabilidad de las transformaciones de texto plano y de texto cifrado.

Metodología
Los autores emplean una combinación de Teoría de la Información Cuántica y Criptografía Abstracta para analizar el protocolo QPKE-QKD con ruido. La metodología se estructura en torno a los siguientes componentes clave:

1. Inyección de Ruido mediante Maleabilidad: El artículo adapta el concepto de maleabilidad, introducido originalmente por Maurer y Tackmann [9] para comparar protocolos de "autenticar y luego cifrar" frente a "cifrar y luego autenticar". Los autores definen transformaciones ruidosas en el espacio del texto plano caracterizadas por tres probabilidades de error: error de reenvío (forwarding error), error de eliminación (deleting error) y error de reconstrucción (reconstruction error). Estos errores se utilizan para modelar el impacto del ruido en el texto cifrado.
2. Distancia de Traza y Lema de Medición Suave (GML): Una herramienta técnica central es la adaptación del Lema de Medición Suave (Gentle Measurement Lemma) de la Teoría de la Información Cuántica [18]. Los autores utilizan este lema para establecer un límite superior en la distancia de traza entre dos estados cuánticos (que representan los experimentos real e ideal) basándose en un límite inferior de la traza de un operador específico. Esto permite la generalización de la función de negligibilidad en presencia de ruido.
3. Máquinas de Tiempo Polinómico Cuántico con Ruido (NQPT): El artículo formaliza el entorno con ruido definiendo máquinas de Tiempo Polinómico Cuántico con Ruido (NQPT) y mapas de Traza Preservadora de Positividad Completamente Positiva (CPTP) con Ruido. Estos objetos reemplazan a sus contrapartes sin ruido para modelar el comportamiento de Alice, Bob y el adversario (Eve) bajo condiciones de ruido.
4. Operadores de Proyección y Descomposición de Estados: El análisis implica la construcción de operadores de proyección ruidosos ($\tilde{\Pi}$) que incorporan términos de ruido (por ejemplo, $|\sigma + \text{ruido}\rangle$) en el operador de proyección estándar $\Pi$ utilizado en el protocolo QPKE-QKD sin ruido. Los autores derivan límites superiores en la distancia de traza comparando las razones entre los operadores de proyección ruidosos y sin ruido, las operaciones de traza, y los estados ket/bra.
5. Enfoque de Teoría de Recursos: El artículo utiliza el marco de la teoría de recursos de [9], definiendo la seguridad y la disponibilidad en términos de la indistinguibilidad de los recursos construidos por los protocolos. Esto incluye el análisis de la composición de protocolos y la indistinguibilidad de experimentos híbridos.

Contribuciones Clave

• Formalización de la Seguridad Eterna con Ruido: El artículo define la "seguridad eterna" para un protocolo QPKE con ruido (Definición 37), estableciendo que la distancia de traza entre experimentos híbridos ruidosos está acotada por una función de negligibilidad dependiente del parámetro de seguridad ruidoso $\lambda'$.
• Generalización de la Función de Negligibilidad: Los autores derivan una relación entre la distancia de traza en el entorno con ruido y la función de negligibilidad $NEGL(\lambda')$. Demuestran que, bajo supuestos específicos sobre el ruido, la función de negligibilidad en el entorno con ruido se relaciona con un umbral de seguridad más alto en comparación con el caso sin ruido.
• Límites de la Distancia de Traza vía GML: Una contribución técnica primaria es la derivación de un límite superior en la distancia de traza utilizando el Lema de Medcción Suave. Los autores demuestran que:
  $$Td(\tilde{Exp}, Exp) \lesssim \sqrt{NEGL(\lambda' - \lambda)}$$
  Esto se logra probando un límite inferior en la traza de un operador específico que involucra la diferencia entre los estados ruidosos y sin ruido ($\tilde{\rho} - \tau$).
• Supuestos de Maleabilidad: El trabajo vincula explícitamente la seguridad del protocolo con la maleabilidad de las transformaciones del texto cifrado. Cuantifica cómo las probabilidades de error de reenvío, eliminación y reconstrucción de las transformaciones ruidosas se relacionan con la brecha del umbral de seguridad entre los protocolos sin ruido ($\lambda$) y con ruido ($\lambda'$).
• Compensaciones de Tiempo de Ejecución Computacional: El artículo analiza las compensaciones entre el tiempo de ejecución computacional de los protocolos con y sin ruido (codificación, decodificación y generación de claves). Sugiere que si el tiempo de ejecución del protocolo con ruido es significativamente mayor, la brecha del umbral de seguridad $\lambda' - \lambda$ escala de una manera específica, potencialmente relacionada con funciones exponenciales o polinómicas de la diferencia de tiempo de ejecución.

Resultados

• Teorema Principal: El artículo demuestra que para un protocolo QPKE-QKD con ruido que satisface condiciones de corrección, la distancia de traza entre los experimentos híbridos ruidosos (inicializados con bits 0 y 1) está acotada por la función de negligibilidad del parámetro de seguridad ruidoso:
  $$Td(\tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 1), \tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 0)) \lesssim NEGL(\lambda')$$
• Corolario sobre Funciones de Ventaja: Los autores muestran que las funciones de ventaja ruidosas para diferentes experimentos híbridos ($\tilde{Adv}(0), \tilde{Adv}(1), \tilde{Adv}(2)$) están todas acotadas por la misma función de negligibilidad $NEGL(\lambda')$, confirmando la consistencia de la definición de seguridad a través de diferentes configuraciones experimentales.
• Límite Inferior de la Traza: El artículo proporciona una derivación detallada que muestra que la traza de un operador específico que involucra la diferencia de los estados ruidosos y sin ruido está acotada inferiormente por una constante multiplicada por el inverso de la función de negligencia, lo cual es un requisito previo para aplicar el Lema de Medición Suave.

Significancia y Reivindicaciones
El artículo afirma proporcionar un marco matemático riguroso para extender la noción de seguridad eterna a la Criptografía de Clave Pública Cuántica con ruido. Al adaptar el Lema de Medición Suave, los autores demuestran que las garantías de seguridad del protocolo sin ruido pueden generalizarse al entorno con ruido, siempre que el ruido se caracterice a través de supuestos de maleabilidad en las transformaciones del texto cifrado.

Los autores enfatizan que, si bien la introducción de ruido generalmente conduce a un umbral de seguridad más alto (lo que implica una garantía de seguridad potencialmente más débil en términos del parámetro $\lambda'$), los límites derivados permiten una comparación cuantitativa entre los protocolos con y sin ruido. El trabajo se presenta como un paso teórico, señalando que, aunque los requisitos para la seguridad incondicional y eterna son difíciles de realizar experimentalmente, el marco propuesto ofrece un punto de partida valioso para analizar las limitaciones de la computación cuántica con ruido en contextos criptográficos. El artículo concluye sugiriendo que los cálculos derivados para acotar la distancia de traza podrían examinarse más a fondo en entornos centrados en enfoques de la teoría de juegos, aunque no propone implementaciones experimentales específicas ni aplicaciones inmediatas más allá del análisis teórico.