美國國家安全局的“量子計算機”什么密碼都能破？

流言說：斯諾登泄漏的文件顯示,美國國家安全局(NSA)正在開發一個“量子計算機”，可以破解幾乎任何類型的加密, 該項目是其總額為7970萬美元的“穿透硬目標”項目的一部分，項目在馬里蘭大學帕克實驗室運作。這種“量子計算機”能夠幫助美國國安局破解任何類型的加密，包括銀行、醫療、商業以及政府的密碼。

回答：

假。量子計算機并不相當于一臺能夠做高速運算的經典的超級計算機。它的出現會威脅到當前的密碼體系，同時我們也有足夠的技術儲備來維持我們的隱私，維護目前的秩序。

論證：

什么是量子計算機？量子計算機并不相當于一臺能夠做高速運算的經典的超級計算機。量子計算機能以高速度解決某些特定的問題，但卻對別的問題無能為力。目前人們找到的高速度的量子算法大體有兩類，一類是解決隱含子群問題的，比如因子分解問題、離散對數問題等，量子計算機在這些問題上有指數級的加速；另一類是量子隨機游走相關的，比如說Grover算法（在O(sqrt(n))時間內搜索大小為n的數據庫）等，量子計算機在這些問題上有多項式級的加速。還有一些比較奇怪的就不說了。在這些特定的問題上，量子計算機能迅速解決問題，但出了這個范圍，目前它跟經典計算機沒什么區別。

會威脅到當前的密碼體系，但并非無所不能

量子計算機能解決的問題，是否會威脅到當前的密碼體系呢？答案是的確會。目前的密碼體系大體有兩種：對稱密碼與非對稱密碼。AES是前一種的例子，RSA是后一種的例子。對稱密碼的話，Grover算法能進行不小的加速，比如說AES-128的密鑰空間是2^128，通過構造適當的可以量子化的數據庫黑盒子，Grover算法能在大約2^64的時間內找到密鑰，而經典計算機則需要大概2^128的時間。不過這個問題并不特別大，換用更長的密鑰就可以了。問題在于非對稱密碼，量子計算機在很短的時間內破解。而偏偏這些算法特別重要，無論是銀行轉賬、身份識別、在線瀏覽，很多都需要非對稱算法來進行密鑰分發與身份驗證。舉個例子，上Gmail時候會自動SSL加密，這個東西就是用RSA來做密鑰分發的。

那么，一旦量子計算機做出來之后，是不是隱私就無處遁形呢？那倒不一定。

學界早就關注這個現象了，也提出了一些能解決這個問題的非對稱密碼體系，比如說基于格（lattice）的體系（比如NTRU）、基于糾錯碼的體系（McEliece），還有基于多變量的體系。這些體系都不依賴于隱含子群問題，所以對量子計算機造成的威脅是免疫的。不過，這些體系各有各不太實用的地方，也有些弱點，所以目前沒有很多人采用。不過一旦足夠規模的量子計算機造出來了，我們也有足夠的技術儲備來維持我們的隱私，維護目前的秩序。