Computer quantistici e NP completezza

-

Leggevo un articolo di Scott Aaronson su "Le Scienze" (la versione italiana di Scientific American) e devo dire che ho trovato molto interessante la sua analisi sui "futuribili" computer quantistici e sui loro limiti. Scott spiega cosa è un computer quantistico, cosa non è, e quello che non sarà mai probabilmente in grado di fare.

Su una cosa non vi è dubbio: la fattorizzazione in numeri primi (che non è un problema NP-completo ma solo NP, anzi per essere precisi ricade nella classe BPQ) è un problema risolvibile dai computer quantistici in un tempo polinomiale, unicamente perché vi sono algoritmi anch'essi quantistici in grado di farlo.

Un computer quantistico quindi non è ancora in grado di risolvere in tempo polinomiale alcun problema NP-completo e questo proprio perché non sono stati elaborati algoritmi efficienti per questo tipo di computer. La congettura "P diverso da NP" rimane quindi tale anche con i computer quantistici. Se però qualcuno elaborerà mai un algoritmo in grado di risolvere in tempo polinomiale un problema in NP-C (con computer quantistico o meno poco importa), allora sarà dimostrato che NP=P.
Insomma i problemi in NP-C possono dormire sonni tranquilli e forse la congettura P diverso da NP verrà prima o poi annoverata come uno dei limiti fisici che esistono in natura. Qualcuno dovrebbe riuscire però a dimostrarla formalmente...


Anche se il problema della fattorizzazione è però quantisticamente trattabile, la sicurezza non è a rischio. Il fatto che un computer quantistico sia in grado in un tempo polinomiale di rompere una cifratura asimmetrica basata sulla fattorizzazione in numeri primi, mostra solo il limite della fattorizzazione come funzione "computazionalmente svantaggiosa". Serviranno quindi solo nuove funzioni che siano anche "quantisticamente svantaggiose".


Per cui come abbiamo dichiarato obsoleto il DES in favore del nuovo AES, un giorno dichiareremo obsoleta la fattorizzazione in favore di altre funzioni più resistenti ai nuovi attacchi.


Commenti

Posta un commento

Post popolari in questo blog

Exploit: icsploit o espluà?

-
Immagine
Non ce la faccio più! Continuo a sentir pronunciare " exploit ", nel senso di " sfruttamento di una vulnerabilità informatica ", in francese: espluà ! E' quasi un pugno nello stomaco! Sebbene il termine inglese derivi dal francese, quando si usa nel contesto della sicurezza informatica, la pronuncia è in inglese, ovvero " ecsploit "o " icsploit " (a seconda che sia un sostantivo o un verbo). E poi visto che la consuetudine è quella di usare termini inglesi nel contesto informatico, e per amore di un unico e non ambiguo vocabolario, usiamo i termini inglesi quando ci riferiamo a cose ben specifiche  e relative all'informatica. Per essere estremamente chiari, se dobbiamo parlare di "SQL Injection" non è che possiamo tradurla come "inoculazione di sequenze maliziose in una istruzione del linguaggio SQL". Non si capisce nulla! Altrimenti torniamo al caro professore che insisteva nel tradurre "Computer" in "...
Continua a leggere

TrueCrypt 5.0: nuova release

-
E' uscita la nuova versione di TrueCrypt 5.0 (ricordo che è Free e Open Source). Importanti le novità: Features : permette di cifrare una intera partizione del disco con un'autenticazione pre-boot; inserita una pipeline per le operazioni di read/write che migliorano le prestazioni fino al 100% su Windows; nuova versione per Mac OS X; GUI per TrueCrypt su Linux; utilizzo di XTS - approvato recentemente come standard IEEE 1619 - per la protezione crittografica di device per lo storage a blocchi; sostituzione dello SHA1 con il più sicuro SHA-512. Bug fix : versione su Linux completamente ridisegnata per sopperire ai problemi dovuti all'aggiornamento del kernel; correzioni di bug e falle di sicurezza. Ho provato la nuova versione sia su Windows XP che su Vista Home Premium. Su XP Professional o Home nessun problema. Potete addirittura non disinstallare la vecchia versione, reinstallando tutto sopra. In Vista consiglio di disinstallare la vecchia versione, riavviare e poi ins...
Continua a leggere

ING Direct: ancora con il PAD numerico rotante!

-
Immagine
Quanti anni saranno che ING Direct ci propina il suo sistema di autenticazione? Avete presente il PAD numerico in cui ogni volta che si accede vengono cambiate le posizioni dei numeri sul tastierino? Negli anni avranno sicuramente cambiato la tecnologia sottostante e le tecniche di sicurezza, tanto è vero che alcuni script client-side inclusi nella pagina, con un breve giro con Firebug, sono generati server-side con URL randomiche (solo nell'ultima parte) e Firebug non riesce a mostrarli. Ma a parte la loro bravura nell'offuscare il codice, perché di offuscamento si tratta, quando si decideranno ad utilizzare un meccanismo di autenticazione a 2 fattori? Una cosa che tu sai + Una cosa che tu hai Potrei suggerire uno degli innumerevoli Token OTP che ormai molte banche danno ai loro correntisti e che li tranquillizzano non poco nell'accesso ai propri conti on-line. Provate a chiedere ad un utente se è più o meno tranquillo con un Token fisico che solo lui detiene e che ogni 30...
Continua a leggere