A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions

Este artículo presenta una codificación QUBO compacta para fórmulas lógicas computacionales que reduce drásticamente el número de variables en algoritmos criptográficos como AES y SHA, aumentando su vulnerabilidad ante futuros annealers cuánticos.

Lo esencial

¡Claro que sí! Imagina que este artículo es como un manual de instrucciones para hacer que los acertijos matemáticos más difíciles sean "pequeños" y fáciles de resolver para una nueva generación de computadoras cuánticas.

Aquí tienes la explicación, traducida a un lenguaje sencillo y con algunas analogías divertidas:

🧩 El Problema: El "Muro de Ladrillos"

Imagina que tienes un rompecabezas gigante (como un código de seguridad o una contraseña). Para resolverlo con una computadora normal, tienes que convertir ese rompecabezas en una lista interminable de reglas de "Sí/No" (lógica booleana).

El problema es que, hasta ahora, convertir estos acertijos en un formato que las computadoras cuánticas puedan entender (llamado QUBO) era como intentar meter un elefante en un coche pequeño. Necesitabas miles de "ladrillos" (variables) extra solo para que la ecuación funcionara. Si el rompecabezas era muy grande (como el cifrado AES-256), el coche se quedaba sin espacio y la computadora no podía resolverlo.

💡 La Solución: "Aplastar" el Elefante

Los autores de este estudio (Gregory Morse y su equipo) han descubierto una forma de comprimir esos rompecabezas. Han creado un método para decir: "Oye, en lugar de usar 100 ladrillos para representar esta parte del acertijo, usemos solo 10, pero de una manera más inteligente".

Lo lograron usando una técnica matemática llamada Programación Lineal Entera (ILP).

• La analogía: Imagina que tienes que empaquetar ropa para un viaje. Antes, ponías cada camisa en una caja separada (muchas variables). Ellos descubrieron que si doblas la ropa de una manera específica (sus nuevos patrones), puedes meter todo en una sola maleta pequeña, ahorrando mucho espacio.

🔑 ¿Cómo lo hicieron? (Los "Trucos" de Magia)

El equipo encontró tres trucos principales para reducir el tamaño de estos acertijos:

1. El Truco del "Aplastamiento de Raíces" (Root Squeezing):
   Imagina que tienes que adivinar un número entre 1 y 10. Normalmente, necesitarías muchos bits para representar ese rango. Ellos descubrieron una fórmula matemática que permite representar ese rango usando un bit menos de lo que creíamos necesario. Es como si pudieras decir "es un número alto" usando solo una señal en lugar de dos.

2. Reutilización de Piezas (Substitution Variables):
   En un acertijo lógico, a veces haces el mismo cálculo varias veces (por ejemplo, "A XOR B"). Antes, la computadora tenía que calcularlo de nuevo cada vez. Ellos crearon un sistema donde, una vez que calculas "A XOR B", guardas el resultado en una "etiqueta" y la reutilizas. Es como tener un atajo en un mapa: en lugar de caminar por todo el bosque, usas un túnel que ya existe.

3. Patrones para Puertas Lógicas:
   Identificaron cómo las computadoras piensan (puertas AND, OR, XOR) y crearon "plantillas" optimizadas para cada una. En lugar de construir cada puerta desde cero con miles de piezas, usaron estas plantillas compactas.

🛡️ El Gran Test: Rompiendo Códigos (Criptografía)

Para demostrar que su método funciona, lo probaron contra los "jefes finales" de la seguridad informática:

• AES: El estándar que protege tus contraseñas y datos bancarios.
• MD5, SHA-1, SHA-256: Los algoritmos que aseguran que un archivo no ha sido alterado.

El resultado fue impresionante:

• Para el cifrado AES-256 (el más seguro), su método redujo el número de variables necesarias en más de 8 veces comparado con métodos anteriores.
• Si antes necesitabas un camión de mudanzas para llevar el problema, ahora cabe en una furgoneta.
• Esto significa que, en el futuro, cuando las computadoras cuánticas sean más potentes, podrían romper estos códigos mucho más rápido de lo que pensábamos, porque el "rompecabezas" que tienen que resolver es mucho más pequeño.

🚀 ¿Por qué es importante esto?

Hoy en día, las computadoras cuánticas (llamadas "recocedores cuánticos") tienen un límite de espacio. No pueden manejar problemas gigantes.

• Antes: Los problemas de criptografía eran demasiado grandes para caber en estas máquinas.
• Ahora: Gracias a esta "compresión", los problemas de criptografía se vuelven lo suficientemente pequeños para que las máquinas cuánticas de hoy y del futuro cercano puedan intentar resolverlos.

🏁 En Resumen

Este papel es como un manual de ingeniería inversa que nos dice: "No necesitas una computadora gigante para romper un código; solo necesitas una forma más inteligente de escribir la pregunta".

Han creado un "idioma" más eficiente para hablarle a las computadoras cuánticas, reduciendo el tamaño de los problemas de seguridad en miles de variables. Esto no solo es un avance matemático, sino una advertencia: la era de la criptografía actual podría estar más cerca de su fin de lo que creíamos, porque ahora podemos hacer que los acertijos sean mucho más fáciles de resolver.

¡Es como si hubieran encontrado la llave maestra que hace que las cerraduras más complejas se abran con una simple chincheta! 🔑✨

Resumen técnico

Aquí presento un resumen técnico detallado del artículo en español, estructurado según los puntos solicitados:

Título: Codificación QUBO compacta de fórmulas de lógica computacional demostrada en construcciones criptográficas

1. El Problema

El objetivo central del trabajo es avanzar en el estado del arte de la Optimización Binaria Cuadrática Sin Restricciones (QUBO), específicamente enfocándose en algoritmos criptográficos.

• Desafío: La formulación de problemas de lógica booleana (como los encontrados en cifrados AES o funciones hash SHA/MD5) en formato QUBO para su resolución en quantum annealers (annealers cuánticos) a menudo resulta en instancias con un número excesivo de variables lógicas y coeficientes de gran magnitud.
• Limitaciones actuales: Los métodos existentes (como las transformaciones de Tseitin estándar) generan matrices QUBO densas y grandes, lo que excede la capacidad de los dispositivos cuánticos actuales (que suelen manejar alrededor de 30.000 variables lógicas) y dificulta la inmersión en hardware con conectividad limitada. Además, los coeficientes grandes pueden superar la precisión numérica del hardware.
• Necesidad: Se requiere una estrategia de codificación que minimice el número de variables de sustitución (ancillary variables), mantenga la matriz QUBO dispersa y reduzca la magnitud de los coeficientes, sin sacrificar la exactitud de la solución (el mínimo global).

2. Metodología

Los autores proponen un enfoque basado en la resolución de problemas de Programación Lineal Entera (ILP) para descubrir patrones de codificación óptimos y reutilizables.

• Búsqueda de Patrones mediante ILP:

  • En lugar de resolver el problema SAT directamente mediante QUBO, utilizan ILP para encontrar las funciones de sustitución óptimas ($s_{valid}$) y los coeficientes de las funciones cuadráticas $g(x, s)$ que mapean fórmulas booleanas a QUBO.
  • El objetivo es encontrar un mapeo donde la función QUBO sea cero solo para las asignaciones válidas (min-terms) y positiva para cualquier otra combinación.
  • Se emplean técnicas de symmetry breaking y búsqueda exhaustiva en instancias pequeñas para generalizar patrones escalables.

• Nuevos Teoremas y Estrategias de Codificación:

  • Teorema de Compresión de Raíces (Root Squeezing Theorem): Demuestran que las restricciones de rango pueden expresarse con un número mínimo de variables auxiliares utilizando un producto de dos funciones lineales enteras cuyas raíces están separadas por una distancia $\le 1$. Esto permite codificar restricciones de rango (como contadores de población) con una variable menos que los métodos tradicionales de cuadrado directo.
  • Codificación de Paridad (XOR): Desarrollan una representación binaria relajada para variables de sustitución que cubren rangos de números impares, optimizando el número de bits necesarios para operaciones XOR de múltiples entradas.
  • Estrategia de "Marcadores Lógicos": Para circuitos complejos, identifican puertas lógicas de múltiples entradas (AND, OR, XOR) y aplican las fórmulas QUBO específicas derivadas de los teoremas anteriores, en lugar de descomponer todo en cláusulas CNF básicas. Esto evita la explosión de variables.

• Aplicación a Criptografía:

  • Se aplican estas técnicas a algoritmos simétricos (AES-128/192/256) y funciones hash (MD5, SHA-1, SHA-256).
  • Para AES, se optimiza la codificación de la caja de sustitución (S-box) descomponiendo la inversión multiplicativa en campos finitos ($GF(2^8)$) en operaciones más pequeñas ($GF(2^4)$ y $GF(2^2)$) y resolviendo sus circuitos booleanos óptimos mediante ILP.
  • Para las funciones hash, se implementa una estrategia de suma modular por bloques para controlar la magnitud de los coeficientes, permitiendo un equilibrio entre el número de variables y la precisión numérica requerida por el hardware.

3. Contribuciones Clave

1. Generalización de Patrones QUBO: Se extiende el trabajo previo para incluir fórmulas de paridad (XOR), estableciendo una base para codificar eficientemente formas normales SAT (CNF, DNF, ANF y PES).
2. Reducción Masiva de Variables: Se demuestra que es posible reducir drásticamente el conteo de variables en comparación con los resultados publicados anteriormente, manteniendo la matriz QUBO dispersa.
3. Optimización de Coeficientes: Se introduce una metodología para limitar la magnitud de los coeficientes mediante la partición de operaciones aritméticas en bloques, facilitando la ejecución en hardware con precisión limitada.
4. Teoremas Fundamentales: La formulación del Root Squeezing Theorem y el Range Encoding Theorem, que proporcionan límites superiores y métodos constructivos para la codificación de restricciones de rango con el mínimo número de variables auxiliares.

4. Resultados

Los autores evaluaron su enfoque en varios algoritmos criptográficos, logrando mejoras significativas frente a la literatura previa (específicamente comparado con [36], [35], [74]):

• AES-256: Lograron una reducción de más de 8 veces en el número de variables en comparación con resultados anteriores. La codificación completa requiere aproximadamente 29.330 variables (para cifrado), lo que representa solo el 12% del tamaño de la mejor codificación previa conocida (~250.000 variables).
• AES-128 y AES-192: Reducciones similares, con tamaños de QUBO de ~21.000 y ~24.000 variables respectivamente, superando ampliamente a métodos anteriores que codificaban solo una caja S-box con más variables que el algoritmo completo en este nuevo enfoque.
• Funciones Hash (MD5, SHA-1, SHA-256):
  • MD5: Reducción a 10.272 variables (con bloques de tamaño 6), frente a ~17.000 en trabajos anteriores.
  • SHA-256: Reducción a 30.255 variables (frente a 47.808 en [36]).
• Características de la Matriz: Las matrices resultantes son altamente dispersas (densidad entre 0.04% y 0.52%) y, aunque algunos coeficientes son grandes en configuraciones de alto rendimiento, se pueden reducir significativamente (hasta 55) sacrificando un aumento moderado en el número de variables (estrategia de bloques pequeños).

5. Significado e Impacto

• Vulnerabilidad Criptográfica: La reducción drástica en el tamaño de las instancias QUBO aumenta la vulnerabilidad de estos algoritmos criptográficos ante futuros quantum annealers. Si los dispositivos actuales pueden manejar ~30.000 variables, la codificación de AES-256 en ~29.000 variables sugiere que la ruptura de estos cifrados mediante annealing cuántico podría ser más cercana de lo que se pensaba, siempre que se pueda encontrar el mínimo global exacto.
• Viabilidad en Hardware Actual: La alta dispersidad de las matrices generadas favorece su inmersión (embedding) en hardware de annealing cuántico con topologías limitadas (como los procesadores de D-Wave).
• Marco General: La metodología no se limita a la criptografía; ofrece un conjunto de bloques de construcción eficientes para codificar cualquier problema de lógica booleana en QUBO, lo cual es crucial para la computación cuántica adiabática en general.
• Límites y Futuro: El trabajo destaca que la búsqueda de circuitos booleanos óptimos para funciones complejas (como la multiplicación en campos finitos) sigue siendo un problema NP-duro y difícil de resolver exhaustivamente, sugiriendo que mejoras futuras en los solucionadores ILP podrían reducir aún más los tamaños de las instancias QUBO.

En conclusión, el artículo presenta un avance metodológico crucial que transforma problemas criptográficos complejos en instancias QUBO manejables y eficientes, poniendo a prueba los límites de la seguridad criptográfica frente a la computación cuántica emergente.