Resumen Técnico: Firmas Digitales con Sombras Clásicas en Computadores Cuánticos de Corto Plazo

Declaración del Problema

Los esquemas tradicionales de firma digital dependen de la existencia de funciones de un solo sentido (OWF, por sus siglas en inglés), como la factorización de enteros (RSA) o problemas basados en retículos (LWE). Estas suposiciones son vulnerables a computadores cuánticos tolerantes a fallos (por ejemplo, el algoritmo de Shor) y son objeto de investigación continua respecto a su seguridad contra adversarios cuánticos. Si bien la mecánica cuántica ofrece primitivas criptográficas alternativas fundamentadas en leyes físicas en lugar de dureza matemática, las propuestas existentes para firmas digitales cuánticas (QDS) suelen requerir la transmisión y el almacenamiento coherente de estados cuánticos como claves públicas. Esta dependencia de la comunicación cuántica de bajo ruido y de memorias cuánticas de larga duración hace que las propuestas actuales sean impracticables para los dispositivos cuánticos de corto plazo.

El desafío central abordado en este trabajo es la realización de un esquema de firma digital cuántica que:

1. No dependa de las OWF ni de la existencia de funciones de un solo sentido.
2. Opere utilizando únicamente comunicación clásica, eliminando la necesidad de memoria cuántica o la transmisión cuántica de claves públicas.
3. Sea factible en hardware de escala intermedia con ruido (NISQ) de corto plazo.

Metodología

Concepto Central: Sombras Clásicas como Claves Públicas

Los autores proponen un esquema de firma donde las claves públicas no son estados cuánticos, sino sombras clásicas de estados cuánticos.

• Clave Secreta: Dos circuitos cuánticos aleatorios, $C_0$ y $C_1$.
• Clave Pública: Sombras clásicas, $S(|C_0\rangle)$ y $S(|C_1\rangle)$, generadas mediante mediciones aleatorizadas de los estados $|C_b\rangle = C_b|0\rangle$.
• Firma: Para firmar un bit $b$, el remitente revela la descripción clásica del circuito $C_b$.
• Verificación: El receptor utiliza las sombras públicas y el circuito revelado para verificar que el circuito $C_b$ produce un estado consistente con las sombras públicas. Esto se logra mediante un protocolo de traslape de sombras (shadow overlap protocol).

Suposición de Seguridad: No-Aprendizaje Computacional (CNL)

La seguridad del esquema descansa en la conjetura de No-Aprendizaje Computacional (CNL) a partir de sombras. Esta conjetura postula que es computacionalmente inviable para un adversario aprender la descripción de un circuito cuántico aleatorio dada solo su sombra clásica (muestras de longitud polinómica de mediciones aleatorizadas).

• Esta suposición es distinta de y más débil que la conjetura estándar de "no aprendizaje de estados", ya que las sombras se derivan de copias del estado mediante mediciones simples.
• El artículo proporciona evidencia teórica de que los algoritmos de aprendizaje existentes (por ejemplo, aquellos basados en inversión local o argumentos de cono de luz) fallan al intentar aprender estos circuitos bajo las restricciones del protocolo (aprendizaje adecuado, geometría arbitraria y acceso solo a sombras).
• Los autores demuestran una separación entre el tiempo requerido para verificar una firma (exponencial en $n$ pero factible para el verificador) y el tiempo requerido para aprender (el circuito, para suplantar/spoof) (exponencialmente más difícil), creando una brecha de seguridad.

Innovaciones Técnicas

Para hacer el esquema viable en hardware ruidoso, los autores introducen dos mejoras técnicas clave:

1. Protocolo de Traslape de Sombras Mejorado: Modifican protocolos de traslape de sombras existentes (basados en la Ref. [30]) utilizando circuitos de Clifford aleatorios en subconjuntos de cúbits en lugar de solo mediciones de Pauli aleatorias. Esto reduce el "tiempo de relajación" ($\tau$) de la cadena de Markov de certificación y disminuye la varianza del estimador, mejorando significativamente la tolerancia al ruido y reduciendo la complejidad de muestreo requerida para la certificación.
2. Detección de Errores Cuánticos (QED): Para superar la infidelidad del hardware, los autores emplean un código de detección de errores tipo Iceberg de múltiples bloques.
   • El código Iceberg codifica $k$ cúbits lógicos en $k+2$ cúbits físicos.
   • Utilizan el fijado de gauge (gauge fixing) para promover ciertos operadores lógicos a estabilizadores, creando cúbits "proxy" que permiten la paralelización de puertas lógicas de un solo cúbit, reduciendo así la profundidad del circuito y los errores de memoria.
   • Este enfoque logra un rendimiento "más allá del punto de equilibrio" (beyond-break-even), donde la fidelidad codificada supera la fidelidad no codificada a pesar de la sobrecarga (overhead).

Resultados Clave

Evidencia Teórica

• Dureza del Aprendizaje: Los autores muestran que los algoritmos conocidos para aprender circuitos poco profundos fallan en satisfacer las condiciones necesarias (aprendizaje adecuado, geometría arbitraria, acceso solo a sombras) para romper el esquema.
• Brecha de Seguridad: Demuestran que para conjuntos de circuitos específicos (diseños aproximados), la complejidad temporal para que un adversario aprenda el circuito mediante polinomios de bajo grado o entrenamiento variacional es exponencialmente mayor que el tiempo requerido para la verificación. Específicamente, muestran que el entrenamiento variacional requiere un número exponencial de consultas para alcanzar la fidelidad objetivo para las profundidades de circuito utilizadas.

Demostración Experimental

Los autores implementaron el protocolo en el procesador de iones atrapados Quantinuum H2 (56 cúbits físicos).

• Parámetros del Circuito: Generaron sombras para estados de 32 cúbits usando circuitos aleatorios con $\ge 80$ puertas lógicas de dos cúbits (correspondientes a $\ge 582$ puertas físicas de dos cúbits).
• Fidelidad: Utilizando el código Iceberg de múltiples bloques con fijado de gauge, lograron una fidelidad certificada de $0.90 \pm 0.01$ con 17,316 muestras.
• Prueba de Concepto: El experimento demostró con éxito la capacidad de distinguir entre un firmante honesto y un adversario. Los autores calcularon que aumentar el tamaño de la muestra por un factor de 19.5 (a ~340k muestras) sería suficiente para alcanzar un parámetro de seguridad donde la probabilidad de que un adversario computacionalmente limitado suplante la firma sea insignificante ($< 10^{-5}$).

Significado y Reivindicaciones

El artículo afirma demostrar la viabilidad a corto plazo de firmas digitales cuánticas que no dependen de OWF ni de comunicación cuántica.

• Independencia de las OWF: El esquema fundamenta la seguridad en la dificultad física de aprender procesos cuánticos, ofreciendo una ruta para la criptografía que permanece segura incluso si las OWF no existen.
• Compatibilidad con NISQ: Al utilizar sombras clásicas y códigos de detección de errores en lugar de corrección de errores completa, el protocolo opera dentro de las capacidades del hardware cuántico ruidoso actual.
• Primitiva Fundamental: El trabajo establece un vínculo entre las firmas digitales cuánticas y los acertijos de un solo sentido (one-way puzzles), una primitiva que permite la construcción de otras de protocolos criptográficos cuánticos (como compromisos de bits no interactivos) sin asumir la existencia de OWF.

Los autores enfatizan que, si bien la demostración actual es una prueba de concepto para una firma de un solo bit, las primitivas subyacentes (certificación de traslape de sombras y detección de errores) son escalables. Señalan que extender esto a mensajes de múltiples bits es posible utilizando códigos de corrección de errores clásicos para reducir los costos de verificación, y que aumentar el tamaño del circuito restauraría aún más la seguridad contra posibles avances futuros en algoritmos de aprendizaje.