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

Il paper presenta un nuovo metodo di codifica QUBO compatto per formule logiche computazionali, applicato con successo ad algoritmi crittografici come AES e SHA, che riduce drasticamente il numero di variabili necessarie e aumenta la vulnerabilità di tali sistemi rispetto ai futuri annealer quantistici.

L'essenziale

Immagina di dover risolvere un enorme puzzle logico. Il tuo obiettivo è trovare la combinazione esatta di pezzi (che possono essere solo "accesi" o "spenti", come interruttori) che fa sì che tutto il puzzle funzioni perfettamente.

Questo è il cuore del problema che gli autori di questo articolo hanno affrontato. Hanno lavorato su un metodo per trasformare questi puzzle complessi (usati nella crittografia, come le chiavi di sicurezza di AES o le funzioni di hash MD5/SHA) in un linguaggio che i computer quantistici (in particolare quelli chiamati "annealer") possono capire e risolvere velocemente.

Ecco come funziona, spiegato con metafore:

1. Il Problema: Il Puzzle troppo grande

Immagina di avere un puzzle con 30.000 pezzi. Se provi a metterlo insieme a mano, ci vorrebbe un'eternità. Se provi a dargli a un computer classico, potrebbe impazzire.
In passato, quando gli scienziati cercavano di trasformare questi puzzle crittografici in un formato che i computer quantistici potessero leggere (chiamato QUBO), il risultato era un puzzle mostruoso: servivano centinaia di migliaia di pezzi aggiuntivi solo per far funzionare la logica. Era come se, per risolvere un enigma semplice, dovessi prima costruire un'intera città di pezzi di ricambio.

2. La Soluzione: L'Architetto Intelligente

Gli autori di questo studio hanno detto: "Fermiamoci. Non abbiamo bisogno di costruire tutta quella città. Possiamo essere più intelligenti."

Hanno sviluppato un nuovo metodo per "impacchettare" la logica. Immagina di avere una stanza piena di scatole (i pezzi del puzzle).

• Il vecchio metodo: Per ogni scatola, ne costruivi una copia di riserva, poi un'altra per sicurezza, e un'altra ancora. Risultato: la stanza era piena zeppa di scatole inutili.
• Il nuovo metodo (di questo paper): Hanno inventato un sistema di "scatole magiche" (chiamate variabili di sostituzione) che possono fare più lavori contemporaneamente. Invece di avere 100 scatole diverse per dire "se A è acceso, allora B deve essere spento", ne usano una sola che cambia forma a seconda di cosa le chiedi.

3. La Magia: La "Squeeze" (Strizzatura)

Il cuore della loro scoperta è una regola matematica che chiamano "Teorema della Strizzatura delle Radici" (Root Squeezing Theorem).
Facciamo un'analogia con un tubo dell'acqua:
Immagina di dover far passare dell'acqua (la soluzione) attraverso un tubo.

• Nel vecchio metodo, il tubo era così largo e pieno di curve inutili che l'acqua faceva fatica a scorrere e serviva un serbatoio enorme per raccoglierla.
• Il nuovo metodo "strizza" il tubo. Rende il percorso più diretto e compatto. Usano una formula matematica che permette a un singolo pezzo di coprire due o più scenari possibili contemporaneamente. È come se una singola chiave aprisse due serrature diverse a seconda di come la giri.

4. I Risultati: Ridurre la montagna a una collina

Hanno applicato questo metodo ai più famosi sistemi di sicurezza del mondo:

• AES (il sistema che protegge le tue carte di credito e i dati bancari).
• SHA e MD5 (le "impronte digitali" digitali dei file).

Il risultato è sbalorditivo:

• Per decifrare un codice AES-256 (uno dei più sicuri), il metodo precedente richiedeva un puzzle di circa 250.000 pezzi.
• Il loro nuovo metodo lo riduce a circa 30.000 pezzi.
• Significato: Hanno ridotto la dimensione del problema di oltre 8 volte. È come se avessero trasformato una montagna di mattoni in una piccola collina.

5. Perché è importante? (Il Futuro)

Perché ci preoccupiamo di ridurre il numero di pezzi?
Perché i computer quantistici attuali sono come giovani atleti: hanno molta forza, ma poche articolazioni. Possono gestire solo un certo numero di pezzi (circa 30.000) prima di andare in tilt.

• Con i vecchi metodi, i computer quantistici non potevano nemmeno iniziare a risolvere questi problemi di crittografia perché il puzzle era troppo grande.
• Con il nuovo metodo, il puzzle è abbastanza piccolo da essere gestito dai computer quantistici di oggi o di domani.

In sintesi:
Gli autori hanno creato un "linguaggio più efficiente" per parlare ai computer quantistici. Hanno dimostrato che, usando un po' di matematica intelligente (risolvendo piccoli problemi di ottimizzazione per trovare i pattern migliori), possiamo comprimere enormi problemi di sicurezza in spazi molto più piccoli.

La conseguenza?
Questo rende gli algoritmi di crittografia attuali più vulnerabili ai futuri computer quantistici. Non significa che la sicurezza crollerà domani, ma significa che dobbiamo correre più velocemente a sviluppare nuove forme di sicurezza "quantum-proof", perché il muro che protegge i nostri dati è stato reso molto più sottile e accessibile da questa nuova tecnica.

È come se avessimo scoperto un modo per entrare in una cassaforte usando un grimaldello sottile invece di un martello pesante: il lavoro è lo stesso, ma ora è molto più facile da fare.

Sommario tecnico

1. Il Problema

L'articolo affronta la sfida di codificare problemi di logica computazionale complessi, in particolare quelli legati alla crittografia (AES, MD5, SHA), nel formato QUBO (Quadratic Unconstrained Binary Optimization).
Il QUBO è fondamentale per l'elaborazione su quantum annealer (annealer quantistici), dispositivi che trovano il minimo globale di una funzione quadratica. Tuttavia, la traduzione diretta di formule logiche (come CNF, DNF, ANF) in QUBO spesso porta a:

• Un numero eccessivo di variabili binarie (variabili di sostituzione o "ancillary variables").
• Matrici QUBO molto dense.
• Coefficienti di grandi dimensioni, che superano la precisione numerica dell'hardware attuale.

Questi fattori limitano la capacità di risolvere problemi crittografici reali, poiché i dispositivi quantistici attuali hanno un numero limitato di qubit logici (circa 30.000) e una precisione limitata. L'obiettivo è ridurre drasticamente il numero di variabili mantenendo i coefficienti bassi e la matrice sparsa.

2. Metodologia

Gli autori propongono un approccio sistematico basato su tre pilastri principali:

A. Formulazione ILP per la Ricerca di Pattern

Invece di utilizzare trasformazioni logiche standard (come Tseitin), gli autori formulano la ricerca di una mappatura ottimale SAT-to-QUBO come un problema di Programmazione Lineare Interi (ILP).

• Si definisce una funzione quadratica $g(x, s)$ con coefficienti interi sconosciuti, dove $x$ sono le variabili di input e $s$ sono le nuove variabili di sostituzione.
• L'obiettivo dell'ILP è trovare coefficienti tali che $g(x, s) = 0$ solo per le combinazioni valide (i "min-term") e $g(x, s) > 0$ per tutte le altre.
• Si utilizza una strategia di "divide-and-conquer" e ricerca esaustiva su piccoli istanze per scoprire pattern generali riutilizzabili.

B. Teoremi di Compressione e Nuovi Pattern

Attraverso la risoluzione di problemi ILP, gli autori hanno derivato due teoremi fondamentali per ridurre il numero di variabili di sostituzione:

1. Teorema del "Root Squeezing" (Schiacciamento delle Radici): Per vincoli di intervallo (es. $L \le \sum x_i \le H$), invece di usare un quadrato diretto $(\sum x_i - T)^2$, si propone il prodotto di due termini lineari: $(\sum x_i - f_1(s)) \cdot (\sum x_i - f_2(s))$. Se le radici di $f_1$ e $f_2$ sono distanti al massimo di 1, il prodotto è sempre non negativo e zero solo quando il vincolo è soddisfatto. Questo permette di codificare un intervallo con una variabile in meno rispetto ai metodi tradizionali.
2. Codifica Parità (XOR): Per le clausole XOR multi-input, viene utilizzata una rappresentazione binaria rilassata della somma, ottimizzando il numero di bit necessari per rappresentare i valori dispari.

C. Strategia di Marcatura Logica (Logic Markers)

Per i circuiti crittografici complessi, gli autori introducono "marker logici" (variabili di sostituzione) sui sottocircuiti complessi (come le S-box o le addizioni modulari). Invece di minimizzare l'intero circuito booleano (problema NP-difficile), si codificano i blocchi funzionali (AND, OR, XOR, addizioni) usando i pattern ottimizzati sopra descritti e si collegano le variabili di output di un blocco alle variabili di input del successivo.

3. Contributi Chiave

• Nuovi Teoremi di Codifica: Introduzione del Root Squeezing Theorem e del Range Encoding Theorem, che dimostrano come ridurre il numero di variabili di sostituzione per vincoli di intervallo e funzioni di popolazione (popcount).
• Generalizzazione delle Forme Normali: Estensione delle tecniche di codifica QUBO per gestire non solo CNF, ma anche DNF e ANF (Algebraic Normal Form), cruciali per la crittografia basata su campi finiti.
• Ottimizzazione delle S-box AES: Applicazione di una ricerca esaustiva (tramite ILP) per trovare la codifica QUBO ottimale per l'inverso moltiplicativo in $GF(2^8)$, riducendo la complessità rispetto alle decomposizioni standard.
• Strategia di Addizione Modulare a Blocchi: Sviluppo di una tecnica per codificare addizioni modulari su grandi numeri (es. 32-bit) dividendo l'operazione in blocchi più piccoli ($B$), bilanciando il numero di variabili con la grandezza dei coefficienti.

4. Risultati Sperimentali

Gli autori hanno applicato la loro metodologia alle funzioni crittografiche più diffuse, ottenendo riduzioni drastiche rispetto agli stati dell'arte precedenti (come quelli riportati in [36]):

• AES-256: Riduzione delle variabili QUBO a 31.242 (decrittazione) e 29.330 (crittografia). Questo rappresenta una riduzione di oltre 8 volte rispetto ai risultati precedenti e costituisce solo il 12% della dimensione delle migliori codifiche esistenti.
• AES-128/192: Riduzioni simili, con dimensioni totali inferiori a quelle richieste per codificare una singola S-box nei metodi precedenti.
• Hash Functions (MD5, SHA-1, SHA-256):
  • MD5: Ridotto a 10.272 variabili (con blocchi di dimensione $B=6$).
  • SHA-256: Ridotto a 30.255 variabili (contro le ~47.800 di lavori precedenti).
• Proprietà della Matrice: Le matrici QUBO generate sono estremamente sparse (densità tra lo 0,04% e lo 0,52%) e mantengono coefficienti gestibili (specialmente quando si usano blocchi più piccoli, anche se ciò aumenta leggermente il numero di variabili).

5. Significato e Implicazioni

• Vulnerabilità Crittografica: La riduzione delle dimensioni QUBO rende gli algoritmi crittografici (come AES-256) significativamente più vulnerabili agli attacchi tramite quantum annealer. Sebbene i dispositivi attuali non abbiano ancora abbastanza qubit per risolvere istanze complete di AES-256, la riduzione di un fattore 8 avvicina questi problemi alla portata di macchine future capaci di gestire ~30.000 variabili logiche.
• Efficienza Computazionale: Il lavoro dimostra che non è necessario risolvere il problema di minimizzazione logica completa (NP-difficile) per ottenere codifiche efficienti; l'uso di pattern ricorrenti e sostituzioni intelligenti è sufficiente per ottenere risultati quasi ottimali.
• Scalabilità: La metodologia fornisce un framework generale per codificare qualsiasi problema di ottimizzazione combinatoria su hardware quantistico, superando i limiti di precisione numerica e di connettività degli attuali annealer.

In sintesi, il paper stabilisce un nuovo standard per la compressione delle formule logiche in QUBO, rendendo la critanalisi quantistica un'ipotesi molto più concreta per il futuro prossimo e fornendo strumenti essenziali per la progettazione di algoritmi resistenti al quantum.