因為量子計算機的到來，對傳統密碼學會有什麼影響呢？

12-31

看了很多量子計算機的文章，那麼問題來了:量子計算機的解密能力有多逆天？對傳統密碼學會產生怎樣的衝擊？

其實首先是需要問：

量子計算機有多逆天？

如果應用於解決傳統問題，無外乎用n個qubit的系統能表示2^n個傳統bit。但是目前的發現告訴我們，量子計算機並不相當於NTM，只能解決BQP類問題，解決不了NP-complete這類問題。

現今設計出來的量子演算法，已經能夠在解決RSA(因式分解)問題和離散對數問題上有著多項式時間複雜度。因此，學界目前的共識是post-quantum-cryptography應該是建立在一些更困難的問題上。

=========2014年12月15日添加細化內容，晚些時候繼續更新==================

首先，細化一下量子計算機在解決傳統問題上有多逆天（以下我儘力用直觀描述，如有錯誤，請不吝指出）

1. Qubit的存儲/表示能力

由於量子疊加態，一個Qubit的狀態可以是|0&>和|1&>兩種基本態的任意概率組合，也就是說，測量結果是0的概率和測量結果是1的概率才是qubit的狀態的描述。

1.1 但是，這個並不相當於同時擁有2個狀態。因為最終的結果需要測量/觀察，而這個會導致疊加態坍縮，也就是說，最終能得到的，仍然只是0或者1。

1.2 Qubit或qubit-system的狀態只有一個(每個測量值在某一時刻只會有一個概率)，所以，n個Qubit不是同時能表示2^n個狀態，而僅僅是這2^n個狀態的某個概率組合。因此，量子計算機不等於NTM

2. 量子計算機與因數分解

說到這個就不能說到Shor-algorithm Shor"s algorithm這個演算法了。如果熟悉Pollard"s p ? 1 algorithm演算法和FFT，這個演算法相對而言不會那麼難理解。原理是如果能知道與N=pq互素的數A在mod N群里的階數(order) r，若r為偶數，則gcd(A^r/2 -1, N) = p或者gcd(A^r/2 +1, N)=p.

找到r的過程在使用Quantum computer下只有poly(n)的複雜度，而且由於pq的關係，與N互素的數很容易找.

3. 量子計算機和離散對數

shor-algorithm中間尋找r只需poly(n), 其實就說明了Zp上的離散對數在quantum computer上不難

4. 量子計算機和ECC離散對數(DH-KE)

部分EC在量子計算機前脆弱無比，

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Quantum_computing_attacks

不過也有安全的

Supersingular Isogeny Key Exchange

綜述圖片如下，來自http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf

那麼有沒有在經典環境下複雜的問題，在Q-computer面前依舊複雜？

答案是有，那就是NP-hard問題。

（題外話，若干出版的、解3-SAT的高效量子演算法的重要假設是，外部觀察者能( 在觀察導致坍縮之前? )分辨得到的觀查結果是否為0向量。http://www.gcn.us.es/4BWMC/vol2/quantumnp.pdf

如果此假設真正成立，再加上3-SAT本身是NPC問題，即可推出P=NP，連lattice-based cryptography都不用研究了。）

Lattice下問題困難程度一覽：

http://crypto.biu.ac.il/winterschool2012/slides/slides-barilan11.pdf 第12頁截圖

SVP、SIVP、GapSVP、uSVP、BDD都是NP-hard問題。

LWE問題可由量子演算法規約至worst case BDD問題

http://crypto.biu.ac.il/winterschool2012/slides/slides-barilan14.pdf

SIS問題可規約至worst case SVP問題

http://crypto.biu.ac.il/winterschool2012/slides/slides-barilan3-4.pdf

所以，基於LWE和SIS的加密/簽名/密鑰交換系統，在量子計算機前，仍舊是安全的。

傳統密碼學概念和證明方法論在這裡依舊適用。其他lattice-based cryptography的進展請移步本問題下 @劉巍然的答案。

一句話:誠摯邀請大家研究lattice based cryptography

============================================

2014.12.08補充

上面的答案其實是昨天坐地鐵回家，看到 @坡下碎石同學， @玄星同學的回答，想抖個機靈湊個熱鬧的。結果剛剛被認真的 @劉天任同學補充了一下，受寵若驚啊…

我個人對量子密碼學其實並非很感興趣的，量子計算機的出現可以讓計算機在多項式時間內解決類似RSA和離散對數問題。這樣，傳統密碼學的很多構造都不再適用。不過，這就類似於雙線性群（Bilinear Groups）出現為了破解基於橢圓曲線上DDH問題的密碼學方案，結果引入了更多新的更好的密碼學方案一個道理，量子計算機概念的出現也使得人們開始研究在量子計算機下依然安全的密碼學方案。這類密碼學方案到現在為止有兩個分支：

量子密碼學。通過量子本身的特性研究密碼學方案，這類方案現在主要研究點是量子密鑰分發。昨天聽了我師兄的博士畢業答辯，並且下來和他聊了聊。其實，量子通信的本質就是不經意傳輸了。因此，人們現在基本上是反過來思考問題：通過不經意傳輸思路來構建密碼學，而非傳統的用密碼學工具構建不經意傳輸。
格密碼學（Lattice-Based Cryptography）。格密碼學是現代密碼學非常重要的分支。Lattice的出現最早是嘗試解決一類特定的困難問題，比如：具有一定特性的背包問題，具有一定特性的整數規劃問題等等。Lattice引入到密碼學中，以前也是為了破解密碼學方案。

說到這裡就要展開說明了。與Lattice有關的最為臭名昭著的當然是Hellman它們看著RSA先構造了加密方案，然後自己潛心研究提出了基於背包問題的密碼學方案，以期望能夠拿到圖靈獎。結果這個
方案被Lattice幹掉了…
後面的事情大家也都知道了，明明是Diffie-Hellman提出了公鑰密碼學的新概念，結果是RSA通過RSA方案拿到了圖靈獎，Diffie和
Hellman估計再也沒有機會了。Lattice後來用於構造更快的加密方案，因為Lattice中的運算只涉及到矩陣加法和乘法，構造的密碼學方案要比RSA快得多，但是Lattice最大的問題是公鑰太大了。

Lattice至此開始了沉寂，畢竟雙線性群（Bilinear Groups）一出，大家都撲向了IBE，HIBE，ABE等等各種Functional Encryption上面去了。僅有的研究格密碼學的學者們也是嘗試在Lattice上面構造Functional Encryption，而犧牲的是公鑰長度。即便如此，Lattice-Based IBE也是在2009年才正式構造完畢。

2009年，一個非常NB的研究出現了，同態加密（Homomorphic Encryption）。同態加密由Gentry在博士論文中提出。而同態加密的基礎就是理想格（Ideal Lattice）。同時，由於雙線性群的密碼學構造被研究的差不多了，最前沿的密碼學家們都開始撲向了Lattice-Based Cryptography。當然，2004年左右，Regev等人提出了一個基於Lattice的密碼學困難問題，Learn With Errof（LWE），這個困難問題使得格密碼學有了自己的密碼學Trapdoor。同時，由於現在知道，LWE困難問題可以在量子計算機下歸約到Lattice中的NPC問題：SVP（Shortest Vector Problem）。因此，人們相信，Lattice-Based Cryptography在量子計算機下應該也是安全的（用Regev在其Survey上說的，就是It is secure in the quantum world (we believe)）。至此，密碼學家們現在廣泛研究Lattice-Based Cryptography，這些密碼學方案都被認為在量子計算機下也是安全的。我們不妨在此列舉一下現在有關的研究熱點，具體的我們就不展開講了：

Lattice-Based Encryption, Signature, etc.
Homomorphic Encryption, Signature, etc.
Multilinear Map.
Functional Encryption with Low Overhead.
Indistinguishability Obscuration.

============================================

啊對了，打個廣告。

我和 @玄星同學想要組織一個知乎上的公鑰密碼學交流群。我們想組織的群是一個可以深入討論密碼學問題，能夠互相給出啟發，給出資料和信息，分享idea以及Possible Solution的群。歡迎大家入群呀~！我們希望我們的群只包含對密碼學感興趣，想深入研究的朋友們，所以只支持受邀入群，條件是下列三項之一：

在知乎上有關密碼學的問題中有精彩的回答。不在於回答的支持和感謝多，而在於是否專業，是否體現出了水平。
在CCF C類以上會議或者C類以上期刊發表過有關公鑰密碼學的論文，這反應出你在密碼學方案設計與證明有著一定的理解。我本人不才，至今只在C類會議ACISP 2014，B類會議ESORICS 2014上發表了論文。C類期刊Security Network Communication（SCN）上一篇論文的Minor Revision，以及International Journal of Security（IJIS）上投稿一篇，基本能中。剩下的投稿，如Information Science等等，投稿了但沒得到確切的信息，就不明確寫了… 如果有B類或者A類會議或者期刊論文的作者加入，當然熱烈歡迎！

歡迎大家入坑… 想加入的話請聯繫我或者 @玄星。

我學密碼學這門課的時候prof專門講了幾節post-quantum computing cryptography 的課，大概就是量子理論，量子理論，量量子計算原理，QKD，shor"s alrgo ，還有quantam safe crypto. 順便吐槽了dwave出的那個偽量子計算機。

最後結論就是，在量子計算機時代，還是有很多加密演算法是能扛住量子計算破解的。

補充 @劉巍然，量子計算對於密碼學的影響主要有兩個方面。

量子計算可以高效的攻破多種「安全」的密碼體系，這裡安全是對傳統計算機而言。最著名的當然是量子計算機可以高速地分解素因數，因此像 RSA 什麼的就不安全了。因此密碼學要研究不能被量子計算攻破的密碼，比如現在很火的 lattice based cryptography，就有可能應付量子計算的攻擊。
量子計算可以提供完美的加密。事實上，量子計算可以阻止竊聽。傳統密碼學中攻擊者可以竊聽傳輸的密文，只要在密文傳輸時拷貝一份即可。但在量子計算下，qubit 是不可複製的，連竊聽都做不到，就不要想破譯的事情了。但密碼學不僅僅是加密，還有驗證、可信計算、零知識等等。即使加密被量子計算解決了，也還有很多可以研究的問題。
量子計算也給密碼學提供了新的可能性。密碼學的各個 topic，基本都可以切換到量子計算模型下再研究一遍。

到時候你需要繼續學量子密碼學。就跟我們現在除了要學經典的移位密碼等之外還要繼續學現代的對稱和非對稱加密一樣。

先放一張圖

接下來是一些抗量子的密碼

(1)Hash-based cryptography.

The classic example is Merkle"s hash-tree public-key signature system (1979), building upon a one-message-signature idea of Lamport and Diffie.

(2)Code-based cryptography.

The classic example is McEliece』s hidden-Goppa-code public-key encryption system (1978).

(3)Lattice-based cryptography.

The example that has perhaps attracted the most interest, not the first example historically, is the Hoffstein–Pipher–Silverman 「NTRU」 public-key-encryption system (1998).

(4)Multivariate-quadratic-equations cryptography.

One of many interesting examples is Patarin"s 「HFE^(v?)」 public-key-signature system (1996), generalizing a proposal by Matsumoto and Imai.

強大的計算力面前傳統賬號密碼成為冗餘的，連銀行卡都不需要密碼了，未來將是公鑰私鑰系統的身份驗證