Algoritmi quantistici: che cosa diventa facile

Uno speedup è un'accelerazione rispetto al miglior algoritmo classico noto. Le slide citano tre algoritmi quantistici, che danno la risposta con errore limitato, non con certezza:

• la trasformata di Fourier, che scompone un segnale nelle sue frequenze, su spazi di dimensione $n$: da $O(n \log n)$ a $O(\log^2 n)$. Lo speedup è esponenziale, ma su un problema già in P; è il mattone dell'algoritmo di Shor;
• la fattorizzazione degli interi con l'algoritmo di Shor: classicamente non si conosce un algoritmo polinomiale, Shor lo è. Il problema sta in NP, probabilmente non è NP-completo, e non si sa se sta in P;
• la ricerca non ordinata con l'algoritmo di Grover: dati un insieme $S$ e una funzione $f$ che vale 0 o 1 e costa tempo $O(m)$, trovare un $x$ con $f(x) = 1$. A forza bruta si prova un elemento dopo l'altro, in tempo $O(m \cdot |S|)$, dove $|S|$ è il numero di elementi; Grover impiega $O(m \cdot \sqrt{|S|})$. Lo speedup è quadratico.

In un elenco telefonico non ordinato di un milione di nomi servono fino a un milione di controlli; con Grover ne bastano dell'ordine di $\sqrt{1.000.000} = 1.000$.

La ricerca di Grover ha proprio la forma di un problema di NP: $S$ è l'insieme dei possibili certificati, che sono esponenzialmente tanti; ogni certificato è corto; $f$ è la verifica, che costa tempo polinomiale. Se la forza bruta classica costa $c^{n^k}$ passi, Grover la porta a circa $\sqrt{c^{n^k}} = c^{n^k/2}$: l'esponente si dimezza. Il problema resta esponenziale, ma a parità di tempo si risolvono istanze circa due volte più grandi. Più il problema è difficile, meno si guadagna: se il classico costa $2^{n^k}$, la taglia risolubile nello stesso tempo cresce solo di un fattore $\sqrt[k]{2}$.

KNAPSACK (Lezione 8, §6): dati $n$ oggetti con pesi e valori, esiste un sottoinsieme con peso totale al più $W$ e valore totale almeno $V$? Grover cerca tra i $2^n$ sottoinsiemi, e controllarne uno costa $O(n)$. Il costo, scritto come nelle slide, è $O(4^{n/2})$: confrontato con il classico scritto nella stessa base, $O(4^n)$, è la radice quadrata. Con i tempi delle slide, in circa 3 ore e 20 minuti il classico arriva a 70 oggetti e Grover a 140. Le istanze reali, però, hanno decine di migliaia di oggetti: restano fuori portata anche con Grover.

Proposizione: ogni problema in NP si risolve quantisticamente, con errore limitato, in tempo $O\big(c^{n^k/2}\big)$ per qualche $c$ e $k$.

È una questione di rapporto tra costo e prestazioni. Le slide propongono quattro domande da porsi, in ordine, per ogni problema:

1. È facile (in P)? Il calcolo classico è molto competitivo e costa decisamente meno: classico.
2. È difficile, ma la taglia è gestibile con algoritmi classici? Il classico può convenire, a seconda di quanto accelera il quantistico.
3. Altrimenti, la taglia è gestibile con un algoritmo quantistico (per gli NP-completi, circa il doppio)? Allora conviene il quantistico.
4. Altrimenti serve una soluzione approssimata, che di solito richiede tempo polinomiale: lì il classico torna competitivo, perché per ora non ci sono risultati sull'approssimazione quantistica.

SORT (ordinare una lista) è in P: caso 1, si usa il classico. KNAPSACK è NP-completo: dipende dalla taglia, quindi caso 2, 3 o 4.

La crittografia simmetrica usa una sola chiave, sia per cifrare sia per decifrare: i due interlocutori devono prima scambiarsela, e lo scambio è rischioso. La crittografia asimmetrica, o a chiave pubblica, usa due chiavi. Funziona come una cassetta delle lettere: chiunque può imbucare, cioè cifrare con la chiave pubblica, ma solo il proprietario può aprire, cioè decifrare con la chiave privata. Per la firma digitale si cifra con la chiave privata. La sicurezza dei cifrari asimmetrici è computazionale: non è impossibile romperli, è che nessuno conosce un algoritmo polinomiale per farlo.

AES è un cifrario simmetrico; RSA e Diffie-Hellman sono asimmetrici.

Se cifrare e decifrare sono operazioni "pratiche" (in P), attaccare il cifrario sta al più in NP: si indovina la chiave e si verifica in tempo polinomiale se è giusta.

Moltiplicare due numeri primi grandi è facile; risalire ai due primi partendo dal prodotto è, per i computer classici, difficilissimo. RSA mette il prodotto nella chiave pubblica e tiene segreti i due primi. Chi conosce i primi fa tutte le operazioni in tempo polinomiale; chi non li conosce dovrebbe fattorizzare. Nei conti, "$a \bmod n$" è il resto della divisione di $a$ per $n$.

Primi $p = 3$ e $q = 11$: $n = 33$ e $\Phi(n) = (3-1)(11-1) = 20$. Si sceglie $e = 3$, che non ha fattori in comune con 20, e si trova $d = 7$, perché $3 \cdot 7 = 21$ diviso 20 dà resto 1. Chiave pubblica $(3, 33)$, chiave privata $(7, 33)$. Il messaggio $m = 4$ si cifra in $4^3 \bmod 33 = 64 \bmod 33 = 31$ e si decifra con $31^7 \bmod 33 = 4$.

Con $n = pq$ e $\Phi(n) = (p-1)(q-1)$ (la funzione toziente di Eulero): $d = e^{-1} \bmod \Phi(n)$, cifratura $c = m^e \bmod n$, decifratura $m = c^d \bmod n$. RSA è sicuro perché non si conoscono algoritmi classici polinomiali né per la fattorizzazione (dato $n$, trovare $p$ e $q$), né per il logaritmo discreto (dati $c$, $n$ e $c^d \bmod n$, trovare $d$), né per il calcolo di $\Phi(n)$ a partire da $n$, che è difficile quanto fattorizzare.

Shor risolve in tempo polinomiale, su un computer quantistico, sia la fattorizzazione sia il logaritmo discreto: entrambi stanno in BQP. Quindi la crittografia asimmetrica (RSA, Diffie-Hellman) diventa violabile, perché non si basa su problemi NP-completi ma su problemi che Shor risolve. Sono a rischio SSL/TLS, HTTPS e le firme digitali. Le alternative sono cifrari basati su problemi NP-completi e la crittografia quantistica. La crittografia simmetrica invece sembra immune: Grover accelera l'attacco a forza bruta (provare tutte le chiavi), ma il costo resta esponenziale, e per tornare al livello di sicurezza di prima basta raddoppiare la lunghezza della chiave.

Con una chiave da 128 bit la forza bruta classica prova circa $2^{128}$ chiavi, Grover circa $2^{64}$. Con una chiave da 256 bit Grover torna a $2^{128}$, e cifrare e decifrare diventano solo un po' più lenti. Nei protocolli reali la chiave pubblica serve solo all'inizio (handshake), per scambiarsi una chiave simmetrica di sessione: è quella fase, insieme alle firme digitali, che va ripensata.

Il messaggio finale ha tre punti. Primo: il computer quantistico non è una bacchetta magica. I problemi difficili, dagli NP-completi in su, restano plausibilmente difficili (è una congettura); quelli da 2-EXP in su restano sicuramente difficili. Secondo: i benefici ci sono. Con Grover si risolvono istanze circa doppie dei problemi NP-completi, e qualche problema che si ritiene né NP-completo né in P, come la fattorizzazione, può diventare facile. Terzo: quando i problemi tecnologici saranno risolti, gli attuali cifrari asimmetrici potranno essere violati in fretta, e bisognerà ripensare le firme digitali e lo scambio iniziale delle chiavi.

Domanda tipo: "SAT sta in PP?". Sì: SAT sta in NP, e NP sta dentro PP. Domanda tipo: "ciò che risolve un computer quantistico richiede solo spazio polinomiale su un computer classico?". Sì: BQP sta dentro PSPACE.

La catena da sapere è

E le tre classi della lezione a confronto: