後量子公鑰密碼正式啟動時間

　　後量子密碼，作為未來 5-10 年逐漸代替 RSA、Diffie-Hellman、橢圓曲線等現行公鑰密碼演算法的密碼技術，正被越來越多的人所瞭解。目前，美國國家標準技術研究所 (NIST) 正在制定的新一代密碼技術標準，正是後量子密碼標準。

1.1.1，後量子密碼是什麼？

　　後量子密碼是能夠抵抗量子計算機對現有密碼演算法攻擊的 新一代密碼演算法。

　　所謂“後”，是因為量子計算機的出現，現有的絕大多數公鑰密碼演算法（RSA、Diffie-Hellman、橢圓曲線等）能被足夠大和穩定的量子計算機攻破，所以可以抵抗這種攻擊的密碼演算法可以在量子計算和其之後時代存活下來，所以被稱為“後”量子密碼。也有人稱之為“抗量子密碼”，說的都是一個意思。英文中的表述是：#34;Post-quantum Cryptography (PQC)#34;，或者 #34;Quantum-resistant cryptography#34;。

1.1.2，為什麼需要？

1）量子計算機很強大，但利用其強大算力的前提是：存在能高效解決問題的量子演算法，否則量子計算機沒什麼用，反而因為其高昂的成本帶來劣勢。資料：5 量子位元的量子計算機造價在千萬美元左右。

2）量子計算機現有的一些強大演算法/應用包括：密碼演算法安全性、數學計算、機器學習等。

3）對於密碼演算法安全性，主要是針對公鑰密碼演算法：

　　3.1）公鑰密碼演算法安全性依賴的數學問題可以被高效的量子演算法所解決。由於底層依賴的數學問題被解決，所以這些公鑰密碼演算法不再安全。這些數學問題包括：離散對數 (及橢圓曲線版本)、大整數分解等。這直接影響目前使用的 RSA、Diffie-Hellman、橢圓曲線等演算法。著名的量子演算法是 1994 年的 Shor#39;s algorithm。

　　3.2）關於對稱密碼演算法和雜湊函式（例如 AES、SHA1、SHA2 等），雖然有量子演算法可以理論上攻破，但這個演算法的影響有限，且有很多限制條件。著名的量子演算法是 1996 年的 Grover#39;s algorithm。

4）對於公鑰密碼演算法，量子計算機對安全性的影響：

　　4.1）完全攻破目前廣泛使用的公鑰密碼演算法

　　4.2）增大引數的長度沒有用。有人說：把 RSA 的長度從 1024 加到 2048 位元甚至更長，不就安全了嗎？答案是：對於現有的經典計算機和演算法，這樣是可以的。但對於量子計算機和演算法，這是徒勞的（除非 RSA 的長度增大到 1GB 或更長。但這樣的話，演算法還能用嗎？對於其他演算法呢？）

　　4.3）需要全新的公鑰密碼演算法

5）對於對稱密碼演算法，量子計算機對安全性的影響：

　　5.1）降低現有演算法的安全性：安全性從 k-bit 降低為 k/2-bit

　　5.2）增大引數的長度有用

　　5.3）把金鑰長度或雜湊的長度加倍即可，例如：AES-128 升級至 AES-256，SHA-256 升級至 SHA-512 等。但這並不是必須的，原因後面會進行介紹

6）攻破 RSA-2048 的預計時間和開銷：2030 年，量子計算機，10 億美元，核電站 (PQCrypto 2014, Matteo Mariantoni 的預估)

複製程式碼

關於量子計算機，再介紹幾個結論：

（1）量子位元數量重要，但更重要的是質量。目前建造的量子計算機（例如 Google 的 72 qubit 晶片）中，qubit，也就是量子物理位元的質量很差。由於量子相干等物理機制，必須引入糾錯機制，但需要成百上千個量子物理位元進行糾錯，來實現一個量子邏輯位元的功能

（2）攻破現有的公鑰密碼演算法需要幾千甚至幾萬個邏輯位元。結合上面一點可以看到，建造量子計算機仍處在很初級的階段

（3）D-Wave 建造的 D-Wave 2000Q “量子計算機” 實際上是量子退火演算法的，並不是真正意義上的普遍適用的量子計算機

（4）對於量子演算法（例如 Grover），需要指數級別的記憶體，因此 Grover 演算法的威脅不如 Shor 的演算法那麼緊迫

複製程式碼

用 NIST 後量子密碼團隊負責人 Dustin Moody 在 AsiaCrypt 2017 會議上的 Talk 概括一下：

可以看到：

（1）公鑰密碼演算法：紅色叉，需要後量子密碼演算法代替

（2）對稱密碼演算法：藍色框，不那麼緊迫需要新演算法代替。可以透過調整引數解決

1.1.3，我們需要什麼樣的？

顯然，是後量子密碼演算法。更準確的說，是後量子密碼技術標準。密碼實踐中的一個重要結論是：不要自己造輪子（除非你是大佬）。我們現在使用 RSA、Diffie-Hellman、橢圓曲線等演算法正是在被定為國際標準後，才逐漸進入應用領域的。

後量子密碼演算法應該：

　　（1）安全：不僅要在現在的計算條件下安全，也要在量子計算機下安全

　　（2）執行速度快：現有的結果顯示，相同安全強度下，後量子密碼的計算速度可以超越現有公鑰密碼的計算速度

　　（3）通訊開銷合理：實踐中幾乎不會使用一個公鑰/密文大小達到幾 M 甚至更大的演算法。目前的 RSA-2048 公鑰大小約為 256 bytes，橢圓曲線大約為 64 bytes。最好的後量子密碼演算法的公鑰大小在 1KB 左右

　　（4）可被用作現有演算法和協議的直接代替，例如：公鑰加密、金鑰交換、數字簽名等

　　（5）更廣應用場景：例如：同態加密 (Homomorphic Encryption)、屬性加密 (Attribute-based Encryption)、函式加密 (Functional Encryption)、不可區分混淆 (Indistinguishability Obfuscation) 等高階密碼學應用