1978 Criptosistema resiste all'attacco quantistico

Nessuno ha costruito un computer quantistico molto più potente di una calcolatrice tascabile, ma ciò non ha impedito alle persone di preoccuparsi delle implicazioni del mondo dell'informatica post-quantistica. I più preoccupati sono le persone che si affidano ai codici crittografici per proteggere le informazioni sensibili. Quando viene acceso il primo computer quantistico di dimensioni decenti, i codici precedentemente protetti come l'algoritmo RSA comunemente usato diventeranno immediatamente decifrabili.

Ecco perché i crittografi si stanno affrettando alla ricerca di codici che saranno sicuri nel mondo post-quantistico. Oggi, Hang Dinh dell'Università del Connecticut e un paio di amici mostrano che i crittografi ne hanno sempre guardato uno. Dicono che un codice poco usato sviluppato dal matematico del CalTech Robert McEliece nel 1978 possa resistere a tutti gli attacchi conosciuti dei computer quantistici.

Innanzitutto, facciamo una distinzione tra codici simmetrici e asimmetrici. I codici simmetrici utilizzano chiavi identiche per crittografare e decifrare un messaggio. I computer quantistici possono accelerare notevolmente un attacco contro questo tipo di codici. Tuttavia, i codici simmetrici hanno una certa protezione. Raddoppiare la dimensione della chiave contrasta questa accelerazione. Quindi è possibile per i creatori di codice rimanere davanti agli interruttori, almeno in teoria. (Anche se in pratica, il denaro sicuro sarebbe sul predatore in questo gioco del gatto e del topo.)

I codici asimmetrici utilizzano chiavi diverse per crittografare e decifrare i messaggi. Nei cosiddetti sistemi di crittografia a chiave pubblica come il popolare algoritmo RSA, una chiave pubblica è disponibile per chiunque possa utilizzarla per crittografare un messaggio. Ma solo chi ha una chiave privata può decifrare i messaggi e questo, ovviamente, è tenuto segreto.

La sicurezza di questi sistemi si basa sulle cosiddette funzioni botola: passaggi matematici facili da eseguire in una direzione ma difficili da eseguire nell'altra. L'esempio più famoso è la moltiplicazione. È facile moltiplicare due numeri per ottenere un terzo, ma è difficile iniziare con il terzo numero e calcolare quali due lo hanno generato, un processo chiamato fattorizzazione.

Ma nel 1994, il matematico Peter Shor ha inventato un algoritmo quantistico in grado di fattorizzare molto più velocemente di qualsiasi controparte classica. Un algoritmo del genere in esecuzione su un computer quantistico decente potrebbe violare tutti i sistemi di crittografia a chiave pubblica noti come un bambino di 4 anni che si scatena a Legoland.

Ecco un'idea di come funziona. Il problema della fattorizzazione è trovare un numero che si divida esattamente in un altro. I matematici lo fanno usando l'idea di periodicità: un oggetto matematico con la periodicità esatta dovrebbe dividere esattamente il numero, nessun altro lo farà.

Un modo per studiare la periodicità nel mondo classico è usare l'analisi di Fourier, che può scomporre un segnale nelle sue onde componenti. L'analogo quantistico a questo è il campionamento di Fourier quantistico e il trionfo di Shor è stato quello di trovare un modo per usare questa idea per trovare la periodicità dell'oggetto matematico che rivela i fattori.

Grazie a Shor, qualsiasi codice che si basa su questo tipo di asimmetria (ovvero quasi tutti i più diffusi sistemi di crittografia a chiave pubblica) può essere craccato utilizzando un attacco quantum fourier.

Il crittosistema McEliese è diverso. Anch'esso è asimmetrico, ma la sua sicurezza non si basa sulla fattorizzazione ma su una versione di un enigma che i matematici chiamano problema del supgruppo nascosto. Quello che Dinh e compagni hanno dimostrato è che questo problema non può essere risolto usando l'analisi di Fourier quantistica. In altre parole è immune agli attacchi dell'algoritmo di Shor. In effetti, è immune a qualsiasi attacco basato sul campionamento di Fourier quantistico.

Questo è un grosso problema. Significa che qualsiasi cosa codificata in questo modo sarà al sicuro quando la prossima generazione di computer quantistici inizierà a masticare i più convenzionali sistemi di crittografia a chiave pubblica. Uno di questi sistemi è Entropy, una rete di comunicazione peer-to-peer progettata per resistere alla censura basata sul crittosistema McEliese.

Ma Entropy è poco utilizzato e ci sono buone ragioni per cui altri hanno resistito al sistema di crittografia McEliese. Il problema principale è che sia la chiave pubblica che quella privata sono alquanto ingombranti: una chiave pubblica standard è una grande matrice descritta da non meno di 2^19 bit.

Questo può sembrare un problema minore ora. È possibile che il sistema McEleise diventi improvvisamente al centro di molta più attenzione più di 30 anni dopo la sua invenzione.

Tuttavia, vale la pena sottolineare che mentre il nuovo lavoro garantisce la sicurezza contro tutti gli attacchi quantistici conosciuti, non fa nulla del genere per i futuri attacchi quantistici. È perfettamente possibile che qualcuno svilupperà un algoritmo quantistico che lo farà a pezzi con la stessa facilità di Shor con l'algoritmo RSA. I nostri risultati non escludono altri attacchi quantistici (o classici), afferma Dinh e co.

Quindi lo scenario più probabile per la ricerca futura è che i crittografi rinnoveranno i loro sforzi in una delle molte altre direzioni che sembrano fruttuose, come gli algoritmi basati su reticolo e la crittografia multivariata.

Ad ogni modo, aspettati di sentire molto di più sulla crittografia post quantistica, a condizione che i poteri che ti consentono.

Rif: arxiv.org/abs/1008.2390 : Il crittosistema McEliece resiste agli attacchi di campionamento Quantum Fourier

nascondere