Quantum Hash Function Based on Spectral Properties of Graphs and Discrete Walker Dynamics

Resumen Técnico: Función de Hash Cuántica Basada en Propiedades Espectrales de Grafos y Dinámica de Caminantes Discretos

Planteamiento del Problema
El artículo aborda la creciente vulnerabilidad de las funciones de hash criptográficas clásicas (p. ej., SHA-256, MD5) ante las amenazas de la computación cuántica. Específicamente, algoritmos como Shor y Grover plantean riesgos existenciales para los estándares actuales al factorizar eficientemente enteros grandes y acelerar búsquedas no estructuradas, respectivamente. Mientras que el Instituto Nacional de Estándares y Tecnología (NIST) está estandarizando la Criptografía Post-Cuántica (PQC), existe la necesidad de esquemas de hashing que sean nativos o resistentes al entorno cuántico, capaces de resistir tanto ataques clásicos como cuánticos. Los enfoques existentes suelen depender de operaciones de bits lineales, las cuales pueden no ofrecer una resistencia suficiente contra las aceleraciones cuánticas o pueden no ser capaces de distinguir entre grafos estructuralmente diferentes que comparten el mismo espectro de autovalores (grafos co-espectrales).

Metodología
Los autores proponen QGH-256, un novedoso algoritmo de hashing espectral que integra la dinámica de caminantes discretos clásica con el análisis espectral de grafos cuánticos. El flujo de trabajo se desarrolla a través de las siguientes etapas:

1. Construcción de Grafos Inducida por el Mensaje:

   • Los mensajes de entrada se convierten a binario UTF-8 y se segmentan en bloques.
   • Un caminante discreto clásico opera sobre una cuadrícula toroidal fija de $4 \times 4$. A diferencia de los paseos aleatorios, la dirección del caminante en cada paso está dictada de manera determinista por los bits del mensaje (específicamente, el primer y último bit de cada bloque determinan la dirección: Norte, Sur, Este o Oeste).
   • El valor decimal de cada bloque sirve como el peso para la arista recorrida.
   • Este proceso genera un grafo no dirigido, ponderado y reproducible $G = (V, E, W)$ para cada mensaje de entrada. Los autores señalan que recuperar el mensaje original a partir del grafo es computacionalmente difícil debido a la pérdida de información direccional en los pesos de las aristas no dirigidas y la complejidad de reconstruir la secuencia de recorrido.

2. Huella Espectral mediante Estimación de Fase Cuántica (QPE):

   • La estructura del grafo se codifica en una matriz Laplaciana $L = D - A$ (Matriz de Grado menos Matriz de Adyacencia).
   • Para utilizar algoritmos cuánticos, $L$ se transforma en un operador unitario $U = e^{iLt}$ mediante la exponenciación de matrices.
   • Se aplica la Estimación de Fase Cuántica (QPE) a $U$. Crucialmente, la entrada al circuito QPE no es un autovector único, sino un estado de superposición definido en la base de nodos del grafo ($|\psi\rangle = \sum \alpha_i |i\rangle$).
   • Debido a que el estado de entrada es una superposición de los autovectores de la Laplaciana, el proceso de QPE actúa como un analizador espectral, descomponiendo el estado en sus componentes de frecuencia (fase). La probabilidad de medir una fase específica es proporcional al cuadrado del solapamiento entre el estado de entrada y el autovector correspondiente.

3. Traza de Calor y Generación de Hash:

   • Los autores computan una "huella espectral" evaluando el valor de la traza de calor $h(t) = \sum |c_k|^2 e^{-t\tilde{\lambda}_k}$ a través de múltiples escalas de tiempo. Esta métrica captura tanto la información de los autovalores como la contribución de los autovectores (a través de los coeficientes $c_k$).
   • Este vector de características es procesado posteriormente y comprimido en un hash binario de 256 bits fijos.

Contribuciones Clave

• Resolución de Colisiones Co-espectrales: Una contribución teórica primaria es la capacidad del método para distinguir entre grafos co-espectrales (grafos con espectros de autovalores idénticos pero estructuras diferentes). Al utilizar un estado de superposición como entrada para QPE, la huella espectral resultante depende de los solapamientos de los autovectores ($|c_k|^2$), no solo de los autovalores. Esto asegura que grafos no isomorfos produzcan huellas distintas incluso si comparten el mismo espectro.
• Eficiencia de Pasos Fijos: Los autores mejoraron algoritmos previos basados en caminantes fijando el número de pasos del caminante (10,000) y ajustando el tamaño del bloque según la longitud del mensaje. Esto asegura que el costo computacional de la fase de generación del grafo sea independiente del tamaño del mensaje de entrada.
• Diseño Nativo Cuántico: El algoritmo aprovecha las propiedades intrínsecas de la mecánica cuántica (superposición y estimación de fase) para generar huellas de alta entropía, posicionándolo como un candidato para la seguridad post-cuántica.

Resultados y Evaluación
El artículo evalúa QGH-256 utilizando un Simulador de Estado de Qiskit con semilla para asegurar resultados deterministas y libres de ruido, reconociendo que el hardware NISQ (Escala Intermedia con Ruido) actual introduciría fluctuaciones que afectarían el determinismo.

• Determinismo: Entradas idénticas produjeron consistentemente hashes de 256 bits idénticos.
• Efecto Avalancha: Un cambio de un solo bit en la entrada (p. ej., "Hello" frente a "Hella") resultó en una distancia de Hamming significativamente alta en la salida, confirmando la sensibilidad a las perturbaciones de la entrada.
• Resistencia a Pre-imágenes: Los autores argumentan que revertir el hash es inviable debido a la complejidad del problema del autovalor inverso del grafo y la ambigüedad introducida por la naturaleza no dirigida del mismo.
• Tiempo de Computación: Se observó que el tiempo de ejecución permanece casi constante independientemente de la longitud del mensaje, atribuido al tamaño fijo de la cuadrícula y al número fijo de pasos del caminante.

Significancia y Reivindicaciones
El artículo afirma que QGH-256 ofrece una alternativa robusta al hashing clásico al integrar propiedades topológicas y dinámicas de grafos.

• Resiliencia Cuántica: Los autores afirman que la dependencia del algoritmo de cálculos espectrales complejos y no lineales (que involucran la exponenciación de matrices y circuitos QPE profundos) crea un "oráculo pesado". Esto aumenta significativamente el costo por iteración para un adversario que intente un ataque de pre-imagen basado en el algoritmo de Grover, lo que potencialmente compensa la aceleración cuadrática que ofrece el algoritmo de Grover.
• Cumplimiento con NIST PQC: El esquema se presenta como capaz de cumplir con los criterios de seguridad de NIST PQC (resistencia a ataques cuánticos), rendimiento (tiempo constante relativo a la longitud del mensaje) e interoperabilidad (salida de 256 bits compatible con la infraestructura existente).
• Perspectiva Futura: Los autores concluyen que, si bien las limitaciones del hardware actual (ruido, decoherencia) requieren la simulación para la validación, este enfoque proporciona una vía viable para desarrollar primitivas criptográficas robustas a medida que maduren la corrección de errores cuánticos y la estabilidad de los cúbits.

El artículo no pretende un despliegue inmediato en hardware cuántico real, sino que posiciona a QGH-256 como un marco teórico y una prueba de concepto validada mediante simulación.