量子計算對橢圓曲線密碼學的效果如何？
我一直在閱讀關於橢圓曲線密碼學的維基百科頁面，我遇到了以下內容。
2015 年 8 月，由於擔心 ECC 受到量子計算攻擊，NSA 宣布計劃用新的密碼套件替換 Suite B。橢圓曲線密碼學
我的問題是，ECC 對量子計算有多脆弱？
橢圓曲線密碼學目前並不容易受到量子計算的影響，因為沒有足夠大和足夠可靠的量子電腦來處理。
但它很容易受到足以執行 Shor 算法的量子電腦的攻擊。所有橢圓曲線密碼學*都是基於找到一個秘密整數的難度 $ n $ 給定標量倍數 $ Q = [n]P = P + \cdots + P $ 一個基點 $ P $ 在橢圓曲線上，比如說 $ E/k\colon y^2 = x^3 + 486662 x^2 + x $ 在哪裡 $ k $ 是素數場 $ \operatorname{GF}(2^{255} - 19) $ , 曲線俗稱 Curve25519。†
在功能強大的量子電腦上，Shor 的算法會迅速找到一個週期 $ (\delta, \gamma) $ 功能的 $ (a, b) \mapsto [a]P - [b]Q $ . 任何此類期限均滿足$$ [a - b n]P = [a]P - [b]Q = [a + \delta]P - [b + \gamma]Q = [a + \delta - (b + \gamma)n]P $$對於任何 $ a $ 和 $ b $ 包括零，所以 $ 0 \equiv \delta - \gamma n \pmod \ell $ ， 在哪裡 $ \ell $ 是順序 $ P $ ，我們可以從中輕鬆恢復 $ n \equiv \delta \gamma^{-1} \pmod \ell $ .
量子比特的數量、門的數量以及計算它的執行時間是順序中比特數量的一個小的多項式函式 $ \ell $ ，在典型的密碼學中約為 256。大多數量子電路將致力於計算標量乘法，就像在經典電腦上計算標量乘法一樣，成本 $ O(\operatorname{poly} \log \ell) $ 量子門就像它的成本 $ O(\operatorname{poly} \log \ell) $ 經典電腦上的時間和記憶體；魔法發生在量子傅里葉變換中，以找到一個週期，它只需要花費 $ O(\log \ell \cdot \log \log \ell) $ 量子門。
面對未來的量子密碼分析，今天的危險主要在於文件和對話的長期保密：例如，具有橢圓曲線 Diffie-Hellman 的 TLS 密鑰協議可能會受到 Shor 算法的攻擊，就像有限域 Diffie-Hellman ，啟用 TLS 會話的追溯解密。（DH 的“前向保密”屬性——或者實際上，所有相關方對會話密鑰的擦除——如果攻擊者能夠破解密鑰協議加密，則毫無用處。）對於身份驗證和簽名，例如Ed25519 簽名，危險是只要你有一個升級路徑，在支持 Shor 的量子電腦變得可行時改變簽名方案。
*我不是在討論基於同源的密碼學，例如 SIDH 或 CSIDH 或 SIKE，它們也涉及橢圓曲線，但它們都是基於橢圓曲線離散對數以外的問題——即使 Shor-有能力的量子電腦是實用的。
†這不是攻擊橢圓曲線密碼學的唯一方法。如SafeCurves中所述，還有許多其他問題需要擔心。但是在設計良好且曲線設計良好的協議中，破解密碼學的最著名方法是計算離散日誌。
一些廣泛使用的 ECC 密碼系統，包括 ECDSA 和 Ed25519、ECDH.. 在理論上很容易受到量子計算的影響，如果它們可用於密碼分析（NSA 術語中的加密相關量子電腦）。這些密碼系統基於離散對數問題，在量子計算假設下，它變成了與未知指數的比特大小相關的次指數。
另一方面，有一些可靠的基於 ECC 的密碼系統是為後量子安全而設計的，例如SIKE。因此，ECC 可能仍然是主流的後量子非對稱密碼學，但以另一種形式出現。
我們不知道什麼時候，如果有的話，量子密碼啟示錄可能會發生。或者如何預測它。到目前為止，幾乎沒有什麼量子電腦比經典電腦做得更好，而且這往往與密碼分析無關。比如：模擬特定量子電腦所在的量子系統，或者（有爭議的）為一小類優化問題找到一個好的解決方案。