No, non lo è.

I computer quantistici possono fattorizzare grandi numeri in modo efficiente, il che consentirebbe di rompere molti dei crittosistemi a chiave pubblica comunemente usati come RSA, che sono basati sulla durezza del factoring.

Tuttavia, ci sono altri sistemi crittografici come la crittografia basata su reticolo che non si basano sulla durezza del factoring e che (per le nostre attuali conoscenze) non sarebbero vulnerabili agli attacchi da un computer quantistico.

Il calcolo quantistico ha molte promesse, ma non è infinitamente potente.

Le affermazioni (esagerate) che hai sentito sono probabilmente basate sul più famoso algoritmo di calcolo quantistico, l'algoritmo di Shor. Questo è un metodo per utilizzare un computer quantistico per scomporre gli interi in numeri primi. A quanto pare, molti schemi di crittografia si basano sul fatto che la scomposizione in fattori di grandi numeri è molto difficile. I messaggi possono essere crittografati abbastanza facilmente in modo tale che solo qualcuno che conosce la scomposizione in fattori primi di un determinato numero possa decrittografarli con un ragionevole sforzo. Se potessi rapidamente fattorizzare grandi numeri, romperesti molti schemi di crittografia attuali.

Tuttavia, ci sono altre tecniche che non sono immediatamente minacciate dai computer quantistici. Se non altro, puoi sempre utilizzare un blocco unico fintanto che il messaggio stesso. Questo è matematicamente indistruttibile, poiché qualsiasi messaggio può essere "decifrato" da quello crittografato con l'ipotesi appropriata alla chiave, quindi non c'è modo per un intercettatore di conoscere il messaggio reale.

Il calcolo quantistico può anche aprire le porte a modi di nuova generazione per trasmettere in modo sicuro le informazioni. Ad esempio, la maggior parte della crittografia oggi è proprio questo: rimescolare il messaggio in modo che solo il destinatario previsto possa capirlo. Ma potrebbero esserci buoni modi quantistici per garantire fisicamente che gli intercettatori non possano accedere alla trasmissione in primo luogo.

In realtà c'è un'intera classe di complessità dedicata alla risposta, che è "no, non può rompere alcun codice". La classe è nota come BQP, o "tempo polinomiale quantistico a errore limitato". È la classe dei problemi decisionali che possono essere risolti da un computer quantistico in tempo polinomiale, con un margine di errore non superiore a 1/3 (questo termine di errore è considerato in una fase di calcolo classica che si verifica dopo la maggior parte degli algoritmi quantistici per verificare che risultati sono corretti).

Si ritiene che BQP abbia le seguenti relazioni con altre complessità:

• Contiene P (Tempo polinomiale)
• Interseca, ma probabilmente non contiene completamente NP (tempo polinomiale non deterministico)
  • Probabilmente non contiene NP-completo (come corollario)
• Sottoinsieme di PSPACE (problemi che sono risolvibili con requisiti di spazio polinomiale)

(La principale incognita in quella lista è che non è ancora noto se P = NP. La lista assume P! = NP, ma se P = NP , chiaramente anche NP e NP-complete farebbero parte di BQP. Inoltre non sappiamo se NP = BQP oppure no. così tanto da scoprire! )

RSA è crackable utilizzando computer quantistici perché il compito di factoring grande composito intorpidito ers è in BQP, come dimostrato dall'algoritmo di Shor. L'algoritmo di Shor è NP (ma non NP-completo). Esistono altri algoritmi NP che si ritiene siano al di fuori di BQP che possono essere utilizzati per la crittografia (la risposta accettata si collega alla crittografia basata su reticolo, che è una di queste classi di algoritmi).

Le risposte finora si sono concentrate sulla crittografia a chiave pubblica, in cui qualcuno pubblica una chiave pubblica che può essere utilizzata per crittografare i messaggi e che non è segreta. I computer quantistici sono noti per essere efficienti nel risolvere molti dei problemi più comunemente usati come base della crittografia a chiave pubblica. Non influenza tutta la crittografia a chiave pubblica, solo gli schemi più popolari; influisce sugli schemi più diffusi.

Tuttavia, la crittografia è molto più importante della chiave pubblica. Si ritiene che gli schemi di crittografia simmetrica, in cui le due parti condividono una chiave segreta, siano soggetti a non più di un aumento di velocità quadratico con i computer quantistici (i computer quantistici possono raggiungere un aumento di velocità quadratico per problemi di ricerca generali, ma non di più). Ciò corrisponde a dimezzare effettivamente la lunghezza della chiave. A differenza dei comuni sistemi a chiave pubblica, è estremamente facile rispondere a metà della lunghezza della chiave: puoi semplicemente raddoppiare la lunghezza della chiave e andare avanti. La crittografia simmetrica è estremamente comune; anche dove viene utilizzata la crittografia a chiave pubblica, viene spesso utilizzata solo per scambiare una chiave con la crittografia simmetrica.

Il sistema simmetrico più comune, AES, ha una variante di chiave a 256 bit che fornisce 128 bit di sicurezza contro i computer quantistici. Altri schemi in fase di sviluppo supportano chiavi a 512 bit, che fornirebbero 256 bit di sicurezza effettiva. Si ritiene che sia i bit a 128 che quelli a 256 bit siano sicuri per il prossimo futuro.

Allo stesso modo, si ritiene che le funzioni hash crittografiche reggano molto bene contro i computer quantistici. C'è lo stesso attacco basato sull'algoritmo di Grover, ma come con le funzioni di crittografia è facile da contrastare.

Quindi, qualsiasi affermazione secondo cui la crittografia diventa priva di significato è totalmente fuori base, perché l'unica cosa che è gravemente colpiti sono i sistemi a chiave pubblica. I sistemi a chiave pubblica sono importanti, ma la crittografia è un campo molto più ampio.

No. Non può esistere un computer X che possa rompere un codice perché l'unico time pad è un codice e un time pad non può essere rotto dall'algoritmo (prova banale nella teoria dell'informazione).

Vorrei aggiungere che i computer quantistici non possono rompere alcun codice esistente perché le loro porte logiche possono eseguire le stesse operazioni delle porte logiche classiche. aggiungono nuove possibilità mantenendo quelle precedentemente possibili nei computer classici.

Poiché i programmi, in sostanza, lavorano su porte logiche, è ragionevole presumere che qualsiasi codice esistente per i classici i computer possono funzionare su un computer quantistico.

Vedi anche cancello quantistico su wikipedia.

Ok, in teoria un computer quantistico potrebbe funzionare in questo modo:

Puoi avviare un calcolo normale e calcolarlo in parallelo per tutto il possibile tasti di input. Ciò significa che la decrittografia di un testo crittografato con la chiave giusta richiede il tempo necessario per decrittografarlo con ogni chiave possibile (con una lunghezza fissa). Ciò significherebbe che tutti i metodi di crittografia tradizionali come AES ecc. Potrebbero essere violati con la stessa rapidità con cui potrebbero essere decrittografati dal detentore della chiave legale.

La parte difficile (dove l'unico time pad eccelle) è come per sapere se il messaggio risultante dalla decrittografia è effettivamente il testo corretto. Ad esempio ti mando il messaggio OK crittografato con AES 256 bit. Ora ci sono 2 ^ 256 chiavi possibili con cui decifrare questo messaggio e tutte daranno un risultato. Molti magari in qualcosa come # § o altri simboli di byte criptici, ma alcune chiavi potrebbero portare a due lettere "WB" e alcune combinazioni potrebbero persino portare a "NO".

Quindi la parte difficile è quindi scoprire qual è il messaggio corretto! Perché il computer quantistico (teorico) alla fine produrrà solo pochi risultati con un'elevata propensione, quindi devi codificare un controllo, che distinguerà se l'output è effettivamente un testo valido. Se il testo è molto più grande della chiave e qualcosa di simile a un semplice inglese, o meglio un formato standard che può essere controllato per integrità, questo potrebbe essere possibile. Ma se ci sono diversi risultati possibili che sembrano validi, un essere umano dovrà risolverli in modo che, nel caso di un blocco una tantum, il codice sia altrettanto buono che indovinare dal nulla. Altri schemi di crittografia potrebbero dover essere adattati per produrre messaggi dall'aspetto valido per chiavi false, ma questo sembra possibile ...

-

Funzionerebbe solo se un vero computer quantistico potesse funzionare in questo modo. Per quanto ne so, non abbiamo prove concrete che un controllo di qualità funzioni effettivamente in questo modo. Quindi forse semplicemente non può essere fatto e non abbiamo nemmeno un problema ;-)