哪些跡象表明量子電腦即將對經典密碼學造成威脅？
有什麼跡象表明量子電腦對商業應用中的經典密碼學構成迫在眉睫的巨大危險？
使經典密碼學由對稱算法（分組密碼、散列）和假設因式分解或離散對數的硬度的非對稱算法組成 $ \Bbb Z_p $ 或橢圓曲線，其參數足夠大，可以針對在世界級經典電腦上執行的經典算法達到安全性。也許，假設可以訪問量子計算領域的所有結果（即使是秘密結果：你是 CIA 分析師，眼睛無處不在）。
如果獎金是下注的 100 倍，我建議“迫在眉睫”是 2 年，“相當大”是值得下注的；但可以隨意參數化或改變它。
請制定合理的論點（最好是定量的），例如，基於對使用各種量子電腦可實現的目標進行分類、從本質上限制該領域進展的因素以及與其他技術進步的比較。
動機：這篇 2018 年 5 月 18 日的文章引用了參與量子電腦開發的研究實驗室主任的話：
“任何想要確保他們的數據受到 10 年以上保護的人現在都應該轉向其他形式的加密”
根據該消息來源，記者寫道：
量子電腦將能夠立即破解受當今最強安全保護的敏感數據的加密 (..) 由於量子電腦技術的進步，這可能會在五年多一點的時間內發生。
傳統密碼學存在三種主要的標準量子威脅：
- 肖爾算法。花費 $ O(\log \ell \cdot \log \log \ell) $ 量子門和 $ O(\log \ell) $ 量子電路中的額外量子位來計算函式的周期 $ f $ 被約束 $ \ell $ . 要計算的量子門的數量 $ f $ 與經典門的數量大致相同，而量子比特的數量大約是經典比特數的兩倍，以實現可逆。
標準範例：
- 修復組 $ G $ 有秩序的 $ q $ ， 說 $ (\mathbb Z/p\mathbb Z)^\times $ 為素數 $ p $ ， 或者 $ k $ -理性點 $ E(k) $ 在某個橢圓曲線上 $ E/k $ 在一個領域 $ k $ . 為了 $ g, h \in G $ ， 定義 $ f(x, y) := h^y g^{-x} $ . 如果 $ h = g^n $ 對於某個整數 $ n $ ， 然後 $ f(x, y) = g^{n y - x} $ 和任何時期 $ (\delta, \eta) $ 的 $ f $ 滿足 $ g^{n y - x} = g^{n (y + \delta) - (x + \eta)} $ 對所有人 $ x $ 和 $ y $ 包括零，所以 $ 0 \equiv n \delta - \eta \pmod q $ ，我們可以從中恢復 $ n \equiv \eta \delta^{-1} \pmod q $ . 因此，通過找到一個時期 $ (\delta, \eta) $ 的 $ f $ , Shor 算法計算離散對數。
- 讓 $ n = pq $ 是兩個秘密大素數的乘積 $ p $ 和 $ q $ . 如果為隨機 $ a \in \mathbb Z/n\mathbb Z $ 期間 $ f(x) = a^x \bmod n $ 是 $ 2r $ 和 $ a^r \not\equiv -1 \pmod n $ ， 然後 $ \gcd(a^r \pm 1, n) \in {p,q} $ , 產生一個非平凡的因子 $ n $ . 如果不是——如果 $ f $ 是奇數，或者如果 $ a^r \equiv -1 \pmod n $ ——然後再試一次 $ a $ . 因此，通過找到一個時期 $ 2r $ 的 $ f $ , Shor 的算法因數整數。
Shor 算法在 2012 年 的目前記錄計算了 $ x \mapsto 4^x \bmod{21} $ ，這是（劇透警告！）3，通過將機器減少到單個量子位和單個 qutrit 並連續計算週期一的位，而不是算法通常需要的兩個控制量子位和五個工作量子位大小一下子給出答案。該記錄與 2001 年 Shor 算法的第一份報告相比沒有太大改進，該報告計算了 2 或 4 個週期 $ x \mapsto a^x \bmod{15} $ 使用 7 個量子位，而沒有使 2012 年的記錄使用更少的量子位的量子位回收。
要將其擴展到數千位，我們需要一台比這更大的量子電腦。我們需要多少個量子比特和量子門有各種估計*$$ cetacean needed $$*. 據稱，IBM 製造了 50 量子比特的量子電腦，Google製造了 72 量子比特的量子電腦，但沒有人報告在它們上成功執行 Shor 算法。 在它威脅到基於阿貝爾隱藏子群的密碼學之前，證明量子電路可以擴展以在少數量子比特之外執行 Shor 算法以找到大於 4 的周期的證據將是必要的第一步。 D-Wave 的絕熱量子電腦不適合執行 Shor 算法。但： 2. 通過優化對因子進行量子退火。給定 $ n = pq $ ， 寫 $ n = \sum_i n_i 2^i $ , $ p = \sum_i p_i 2^i $ ， 和 $ q = \sum_i q_i 2^i $ . 比特的知識 $ n_i $ 的 $ n $ 產生未知位的二次約束系統 $ p_i $ 和 $ q_i $ 的 $ p $ 和 $ q $ . 這是一個系統 $ O(\log n) $ 方程在 $ O(\log n) $ 未知數。使用經典計算優化掉一些未知變數以減少約束系統。例如，我們可以假設 $ p_0 = q_0 = p_{\lambda-1} = q_{\lambda-1} = 1 $ 由於因子是奇數且大小已知，因此 $ \lambda $ 是因子的大小，對於 2048 位模數，通常為 1024。然後在絕熱量子電腦上使用量子退火來找到 $ p_i $ 和 $ q_i $ 最小化 $ (n - pq)^2 $ 和 $ O(\log^2 n) $ 量子比特。
2018 年通過退火分解因子的目前記錄使用 94 個量子位來編碼 376289 的優化問題，以及超過 1000 個額外的量子位來實現 D-Wave 2000Q 的優化。這篇論文估計用這種方法分解目前經典 RSA-768 記錄的量子比特數是 147456，而這個“RSA-19”問題需要 94 個量子比特——這還不包括額外的 > 1000 個量子比特需要在 D-Wave 機器上實現程序。（我不清楚這些是否計入 $ O(\log^2 n) $ 為這種方法宣傳的增長曲線，但我認為它們是。）
一篇論文指出，其他整數在“作者不知情的情況下”被先前方法的相同方法意外分解，但這意味著其他整數實際上具有相同的約束集；它並不意味著在 RSA 密鑰生成中選擇的隨機半素因式分解成功的高機率成本。
D-Wave 的電腦似乎越來越大，但據我所知，與解決優化問題的任何專用硬體*相比，它們是否真的提供了量子加速仍然不清楚。*即使他們這樣做了，也不清楚作為變數或約束數量的函式的求解時間的比例是多少，似乎沒有人試圖解決這個問題，除非將曲線擬合到小樣本實驗中。 回答這些問題——量子退火是否比專用硬體上的經典退火更快，以及基於優化的因式分解的求解時間如何擴展？——在這項技術甚至開始威脅基於因式分解的密碼學之前，這是必要的第一步。 3. 格羅弗算法。花費 $ O(2^{n/2}) $ 時間在輸入的量子疊加中評估布爾電路以找到其中的原像 $ O(2^n) $ 可能性。
有一些關於實驗實現的文獻*$$ cetacean needed $$，包括將其與量子電路中的基於優化的因式分解相結合，而不是在絕熱量子電腦上$$ cetacean needed $$*，但我現在沒時間討論這個了。
如果過於保守，Grover 算法的緩解措施已廣為人知$$ cetacean needed $$*，通過增加對稱密鑰和散列大小。* Grover 的算法原則上可以威脅使用 Grover-ECM 的基於因式分解的密碼學*$$ cetacean needed $$，再次需要將素數大小加倍，但據我所知，它並沒有改善對現代橢圓曲線密碼學的攻擊$$ cetacean needed $$*.
我不相信我們可以提前 2 年左右發出可靠的警告。首先是大量的研究被分類。美國國家安全域沒有告訴任何人研究進展如何。Benyamin Netanyhu 剛剛公開表示以色列應該專注於“量子”研究。你認為摩薩德正在分享它的進步嗎？
美國國家安全域能領先世界多遠？很多。IBM 的某個人發現了差分密碼學，而在 Biham&Shamir 重新發現它之前，NSA 將其保密了將近 20 年。
我不認為 NSA 在 Quantom 計算方面領先世界 20 年，但即使是現在也不能確定他們在哪裡。
目前我們不知道如何建構量子電腦，我們不知道如何將足夠多的 q 位放在一起並在足夠多的操作中保持它們的連貫性。事實上，我們離實用的量子電腦還差得很遠。
在我們到達那里之前，我們可能至少需要一個突破和一些漸進的改進。突破會公開嗎？不知道。如果我們取得突破，在量子計算（q 位/相干操作數/時鐘速度/…）中開始穩定的 Moor 風格增長，我們將能夠預測現代密碼學何時會面臨風險。可能會有幾個月或幾年的警告。
但也許需要兩次突破？我們在前一種情況下進行了第一次和每一次恐慌，但直到十年或兩年後第二次突破出現，我們最終才會取得太大進展。
會是哪一個？我不知道。不要認為任何人都這樣做。
不過我很高興我們已經在尋找 Quantom 後的替代品。
*回答是因為我覺得這很有趣，儘管它主要是基於意見的問題。