Computer quantistici: la fine della crittografia?

Annuncio pubblicitario

L'informatica quantistica è una di quelle tecnologie così arcane che i personaggi televisivi lo lasciano cadere quando vogliono sembrare intelligenti.

Il calcolo quantistico come idea esiste da un po 'di tempo: la possibilità teorica è stata originariamente introdotta da Yuri Manin e Richard Feynman nel 1982. Negli ultimi anni, tuttavia, il campo si è avvicinato in modo preoccupante alla praticità.

Aziende come Google e Microsoft, così come agenzie governative come la NSA, perseguono febbrilmente i computer quantistici da anni. Una società chiamata D-Wave ha prodotto e vende dispositivi che (mentre non sono computer adeguati e possono farlo eseguono solo pochi algoritmi) sfruttano le proprietà quantistiche e rappresentano un altro passo in avanti sulla strada verso a completamente Turing-complete Qual è il test di Turing e sarà mai battuto?Il test di Turing ha lo scopo di determinare se le macchine pensano. Il programma Eugene Goostman ha davvero superato il test di Turing o i creatori hanno semplicemente imbrogliato? Leggi di più macchina quantistica.

Non sembra irragionevole affermare che potrebbero verificarsi scoperte che consentiranno di costruire il primo computer quantistico su larga scala entro un decennio.

Allora perché tutto l'interesse? Perché dovresti preoccuparti? I computer diventano sempre più veloci Qual è la legge di Moore e cosa ha a che fare con te? [MakeUseOf Explains]La sfortuna non ha nulla a che fare con la Legge di Moore. Se questa è l'associazione che hai avuto, la stai confondendo con la Legge di Murphy. Tuttavia, non eri lontano perché la Legge di Moore e la Legge di Murphy ... Leggi di più - cosa c'è di così speciale nei computer quantistici?

Per spiegare perché queste macchine sono così importanti, dovremo fare un passo indietro ed esplorare esattamente cosa sono i computer quantistici e perché funzionano. Per iniziare, parliamo di un concetto chiamato "complessità di runtime".

Che cos'è la complessità del runtime?

Una delle grandi sorprese dei primi tempi dell'informatica è stata la scoperta che, se si dispone di un computer che risolve un problema di una certa dimensione in un certo periodo di tempo, il raddoppio della velocità del computer non consente necessariamente di affrontare i problemi due volte grande.

Alcuni algoritmi aumentano nel tempo totale di esecuzione molto, molto rapidamente con l'aumentare della dimensione del problema - alcuni algoritmi possono essere completati rapidamente dati 100 punti dati, ma il completamento dell'algoritmo dato 1000 punti dati richiederebbe un computer delle dimensioni della Terra che corre per un miliardo anni. La complessità del runtime è una formalizzazione di questa idea: esamina la curva della velocità con cui cresce la complessità di un problema e utilizza la forma di quella curva per classificare l'algoritmo.

In genere, queste classi di difficoltà sono espresse come funzioni. Un algoritmo che diventa proporzionalmente più difficile quando il set di dati su cui lavora aumenta (come una semplice funzione di conteggio) si dice che sia una funzione con una complessità di runtime di "n” (come in, ci vuole n unità di tempo da elaborare n punti dati).

In alternativa, potrebbe essere chiamato "lineare", perché quando lo si rappresenta, si ottiene una linea retta. Altre funzioni potrebbero essere n ^ 2 o 2 ^ n o n! (n fattoriale). Questi sono polinomiali ed esponenziali. Negli ultimi due casi, quelli esponenziali crescono così rapidamente che in quasi tutti i casi non possono essere risolti per nulla tranne che per esempi molto banali.

Complessità runtime e crittografia

Se stai ascoltando queste cose per la prima volta e sembra insignificante e arcano, proviamo a fondare questa discussione. La complessità del tempo di esecuzione è fondamentale per la crittografia, che si basa sul rendere la decodifica molto più semplice per le persone che conoscono una chiave segreta rispetto a quelle che non lo fanno. In uno schema crittografico ideale, la decrittografia dovrebbe essere lineare se si dispone della chiave e 2 ^ k (dove k è il numero di bit nella chiave) se non lo fai.

In altre parole, il miglior algoritmo per decrittografare il messaggio senza la chiave dovrebbe essere semplicemente indovinare possibili chiavi, che è intrattabile per chiavi lunghe solo poche centinaia di bit.

Per la crittografia chiave simmetrica (in cui le due parti hanno la possibilità di scambiare un segreto in modo sicuro prima di iniziare la comunicazione) questo è abbastanza facile. Per la crittografia asimmetrica, è più difficile.

La crittografia asimmetrica, in cui le chiavi di crittografia e decrittazione sono diverse e non possono essere calcolate facilmente l'una dall'altra, è una matematica molto più difficile struttura da implementare rispetto alla crittografia simmetrica, ma è anche molto più potente: la crittografia asimmetrica ti consente di avere conversazioni private, anche con un tocco eccessivo Linee! Ti consente anche di creare "firme digitali" per consentirti di verificare da chi proviene un messaggio e che non è stato manomesso.

Questi sono strumenti potenti e costituiscono la base della privacy moderna: senza crittografia asimmetrica, gli utenti di dispositivi elettronici non avrebbero una protezione affidabile contro occhi indiscreti.

Poiché la crittografia asimmetrica è più difficile da costruire rispetto a quella simmetrica, gli schemi di crittografia standard attualmente in uso non sono così efficaci come potrebbero essere: lo standard di crittografia più comune, RSA, può essere decifrato se riesci a trovare in modo efficiente i fattori primi di un numero. La buona notizia è che questo è un problema molto difficile.

L'algoritmo più noto per il factoring di numeri grandi nei numeri primi dei componenti è chiamato setaccio del campo dei numeri generali e ha una complessità di runtime che cresce un po 'più lentamente di 2 ^ n. Di conseguenza, le chiavi devono essere circa dieci volte più lunghe per fornire una sicurezza simile, cosa che le persone normalmente tollerano come costo per fare affari. La cattiva notizia è che l'intero campo di gioco cambia quando i computer quantistici vengono gettati nel mix.

Computer quantistici: cambiare il gioco Crypto

I computer quantistici funzionano perché possono avere più stati interni contemporaneamente, attraverso un fenomeno quantistico chiamato "sovrapposizione". Ciò significa che possono attaccare contemporaneamente diverse parti di un problema, divise tra le possibili versioni dell'universo. Possono anche essere configurati in modo tale che i rami che risolvono il problema finiscano con la massima ampiezza, in modo che quando apri la scatola su Il gatto di Schrodinger, la versione dello stato interno che è più probabile che ti venga presentato è un gatto dall'aspetto compiaciuto con in mano un decifrato Messaggio.

Per ulteriori informazioni sui computer quantistici, controlla il nostro recente articolo sull'argomento Come funzionano i computer ottici e quantistici?The Exascale Age sta arrivando. Sai come funzionano i computer ottici e quantistici e queste nuove tecnologie diventeranno il nostro futuro? Leggi di più !

Il risultato è che i computer quantistici non sono solo linearmente più veloci, come i normali computer: ottenere due o dieci o cento volte più veloce non aiuta molto quando si tratta di crittografia convenzionale che sei centinaia di miliardi di volte troppo lento per elaborarlo. I computer quantistici supportano algoritmi con complessità di runtime in crescita minore di quanto altrimenti possibile. Questo è ciò che rende i computer quantistici sostanzialmente diversi dalle altre tecnologie computazionali future, come calcolo di grafene e memrister L'ultima tecnologia informatica che devi vedere per credereScopri alcune delle più recenti tecnologie informatiche destinate a trasformare il mondo dell'elettronica e dei PC nei prossimi anni. Leggi di più .

Per un esempio concreto, l'algoritmo di Shor, che può essere eseguito solo su un computer quantistico, può fattorizzare grandi numeri in log (n) ^ 3 tempo, che è drasticamente migliore del miglior attacco classico. L'utilizzo del setaccio del campo numerico generale per fattorizzare un numero con 2048 bit richiede circa 10 ^ 41 unità di tempo, il che equivale a più di un trilione di trilioni di trilioni di miliardi. Utilizzando l'algoritmo di Shor, lo stesso problema richiede solo circa 1000 unità di tempo.

L'effetto diventa più pronunciato più a lungo sono i tasti. Questo è il potere dei computer quantistici.

Non fraintendetemi: i computer quantistici hanno molti potenziali usi non malvagi. I computer quantistici possono risolvere efficacemente il problema del venditore ambulante, consentendo ai ricercatori di costruire reti di spedizione più efficienti e progettare circuiti migliori. I computer quantistici hanno già usi potenti nell'intelligenza artificiale.

Detto questo, il loro ruolo nella crittografia sarà catastrofico. Le tecnologie di crittografia che consentono al nostro mondo di continuare a funzionare dipendono dal problema di fattorizzazione dei numeri interi che è difficile da risolvere. RSA e i relativi schemi di crittografia sono ciò che ti consente di fidarti del fatto che sei sul sito Web giusto, ovvero i file che hai il download non è pieno di malware e che le persone non stanno spiando la tua navigazione in Internet (se lo stai utilizzando Tor).

La crittografia mantiene il tuo conto bancario al sicuro e protegge l'infrastruttura nucleare del mondo. Quando i computer quantistici diventano pratici, tutta quella tecnologia smette di funzionare. La prima organizzazione a sviluppare un computer quantistico, se il mondo lavora ancora sulle tecnologie che usiamo oggi, si troverà in una posizione spaventosamente potente.

Quindi l'apocalisse quantistica è inevitabile? C'è qualcosa che possiamo fare al riguardo? A quanto pare... sì.

Crittografia post-quantistica

Esistono diverse classi di algoritmi di crittografia che, per quanto ne sappiamo, non sono significativamente più veloci da risolvere su un computer quantistico. Questi sono noti collettivamente come crittografia post-quantistica e forniscono qualche speranza che il mondo possa passare a sistemi crittografici che rimarranno sicuri in un mondo di crittografia quantistica.

I candidati promettenti includono la crittografia basata su reticolo, come Ring-Learning With Error, che deriva la sua sicurezza da un complesso dimostrabile problema di apprendimento automatico e crittografia multivariata, che deriva la sua sicurezza dalla difficoltà di risolvere sistemi molto grandi di equazioni. Puoi leggere di più su questo argomento sul Articolo di Wikipedia. Attenzione: molte di queste cose sono complesse e potresti scoprire che il tuo background matematico deve essere rafforzato considerevolmente prima di poter davvero scavare nei dettagli.

Il risultato di tutto ciò è che i cryptoschemes post-quantici sono molto interessanti, ma anche molto giovani. Hanno bisogno di più lavoro per essere efficienti e pratici, e anche per dimostrare che sono sicuri. Il motivo per cui siamo in grado di fidarci dei cryptosystems è perché abbiamo lanciato abbastanza geni clinicamente paranoici su di loro per abbastanza tempo che ormai evidenti carenze sarebbero state scoperte e che i ricercatori hanno dimostrato varie caratteristiche che le rendono forte.

La crittografia moderna dipende dalla luce come disinfettante e la maggior parte degli schemi crittografici post-quantici sono semplicemente troppo nuovi per fidarsi della sicurezza mondiale. Ci stanno arrivando, però, e con un po 'di fortuna e un po' di preparazione, gli esperti di sicurezza possono completare il passaggio prima che il primo computer quantistico sia mai online.

Se falliscono, tuttavia, le conseguenze possono essere disastrose. Il pensiero di chiunque abbia quel tipo di potere è inquietante, anche se sei ottimista sulle loro intenzioni. La domanda su chi sviluppa per primo un computer quantistico funzionante è una questione che tutti dovrebbero guardare con molta attenzione mentre ci muoviamo nel prossimo decennio.

Sei preoccupato per l'insicurezza della crittografia per i computer quantistici? Qual è la tua opinione? Condividi i tuoi pensieri nei commenti qui sotto!

Crediti immagine: Sfera binaria Via Shutterstock