Lunedì Valsorda ha finalmente dato sfogo ad anni di frustrazione, alimentati da incomprensioni ampiamente diffuse. Articolo del blog Titolo “I computer quantistici non rappresentano una minaccia per le chiavi simmetriche a 128 bit.”
“C’è un malinteso comune secondo cui i computer quantistici ‘dimezzeranno’ la sicurezza delle chiavi simmetriche, richiedendo chiavi a 256 bit per una sicurezza a 128 bit”, ha scritto. “Questa non è una spiegazione accurata della velocità offerta dall’algoritmo quantistico, non si riflette in alcun ordine di consenso e rischia di distogliere energia e attenzione dal lavoro di transizione post-quantistico veramente necessario.”
Questa è la parte facile dell’argomento. La parte molto più difficile è la matematica e la fisica che lo spiegano. Al suo livello più alto, ciò si riduce a una differenza fondamentale tra il modo in cui funziona l’algoritmo di Grover rispetto al modo in cui funziona la ricerca con forza bruta sui computer classici. I computer classici possono eseguire più query contemporaneamente, una capacità che consente di suddividere attività di grandi dimensioni in parti più piccole per completare l’attività complessiva più rapidamente. A differenza dell’algoritmo di Grover, è richiesto un calcolo seriale di lunga durata, in cui ogni ricerca viene eseguita una alla volta.
“Ciò che rende speciale Grover è che il suo vantaggio rispetto agli algoritmi non quantistici diminuisce man mano che lo si parallelizza”, ha detto Valsorda in un’intervista. Ha continuato:
Visualizza questo con numeri più piccoli, diciamo che una serratura ha 256 combinazioni possibili, un attacco tipico ne proverebbe 256. Decidi che è troppo lungo, quindi prendi tre amici e provi 64 ciascuno. “Questa è la parallelizzazione classica. Con Grover puoi teoricamente provare √256)=16 di fila, ma se è ancora troppo lungo e chiedi di nuovo aiuto a tre amici. Tutti devono provare √256/4)=8.
Quindi hai un totale di 8*4=32 tentativi, che è più dei 16 che avresti fatto da solo! Chiedere aiuto per parallelizzare l’attacco rallenta l’attacco nel suo complesso. Questo non è il caso degli attacchi classici.
Naturalmente i numeri sono enormi, ma se imponiamo qualsiasi vincolo ragionevole all’attaccante (come dover finire una corsa in 10 anni), il lavoro totale diventa molto più grande di 264.
Inoltre, 264 Non ho mai avuto il numero esatto, perché finge di poter eseguire AES come una singola operazione su un singolo qubit. È in qualche modo ortogonale. La combinazione di queste due osservazioni trasforma il costo effettivo in 2104 Dare o avere, è oltre la soglia di sicurezza.
Sophie Schmig, ingegnere senior di crittografia presso Google, lo spiega in questo modo:
