為什麼基於格的密碼學被認為難以對抗量子電腦？

為什麼基於格的密碼學被認為難以對抗量子電腦？

錯誤學習 (LWE) 問題（簡化為 SVP）只是一個例子。

你能提供一些硬度的直覺嗎？

為什麼基於格的密碼學被認為難以對抗量子電腦？

因為還沒有人開發出打破這些加密原語的量子算法。

希望我們能做得更好，但這是我們目前最好的。我們相信這些原語是抗量子的，因為沒有人提供其他證據。

我不知道這個問題的好答案。有“部分答案”，但不是很好。儘管如此，它們是我用來（模糊地）解釋事物的東西，是對不研究量子算法的晶格感興趣的人。

第一的

Grover 的算法非常通用，適用於很多情況，所以我很難相信量子電腦不會提供某種加速。

聲稱並不是說量子算法沒有得到加速（他們有），而是只有在有限的情況下，它們才能得到所謂的超多項式加速。對於一個問題 $ P $ ， 讓 $ T_c $ 和 $ T_q $ 是最好的經典和量子算法的執行時間。的加速_ $ P $ 是函式 $ f(x) $ 這樣 $ f(T_q) = T_c $ .

例如，Grover 搜尋通常給出二次 ( $ f(x) = x^2 $ ) 應用於問題時的加速。這意味著如果你有一個經典的執行時間算法 $ T_c $ ，你一般會得到一個執行時間的量子算法 $ \sqrt{T_c} $ . 對於密碼學問題，我們一般希望 $ T_c = 2^{an} $ 對於一些常數因子 $ a $ . 我們可以通過重新參數化來保持安全性（在存在二次量子加速的情況下） $ n\mapsto 2n $ . 事實上，我相信這是使用 AES256 而不是 AES128 的動機，無論何時你看到有人這樣做。

那麼什麼問題承認超多項式量子加速？不幸的是，我不知道有什麼好的一般理論。兩個尚未解決的顯著問題

1. 圖同構問題，以及
2. LWE。

當然，問題很多，很多量子電腦大概都不知道怎麼解決。為什麼要提到這兩個？答案是它們可以被視為隱藏子群問題的實例。我不會在技術上對此進行定義，但它是某個組參數化的（一般）問題 $ G $ . 通過適當地設置這個組 $ G $ 是各種數量，一個恢復（基本上）

1. 整數分解，
2. 離散對數問題，以及
3. 其他允許大量子加速的問題（但在密碼學上不太為人所知）。

這就是說存在組 $ G_{factoring}, G_{dlog}, G_{graph-iso}, G_{LWE} $ 這樣解決隱藏子群問題 $ G_P $ 足以解決 $ P $ . 我們至少可以說這些群體 $ G_{factoring}, G_{dlog} $ 有一些相似之處 $ G_{graph-iso} $ 和 $ G_{LWE} $ 不？答案是肯定的。

特別是，一項研究將 Shor 算法推廣到了阿貝爾隱子群問題，所以如果/當 $ G_P $ 是一個阿貝爾群， $ P $ 在 $ \mathsf{BQP} $ . 這不是雙重暗示——明天有人可能會為非阿貝爾隱藏子群問題放棄一個有效的算法。但是，它仍然可以被視為指向至少限制（目前）技術的一些數學結構。作為記錄， $ G_{LWE} $ 是一個二面體群，並且 $ G_{graph-iso} $ 是一個對稱群。

雖然這是你可以給予的動力（人們經常這樣做），但我個人並不確定它是否有好處。它有點指向“LWE 是安全的，因為圖同構是另一個難題”。但是圖同構是一個著名的簡單難題——它可以經典地在擬多項式時間內解決。也許將 LWE 與（相對簡單的）經典問題進行比較並不是 LWE 最討人喜歡的地方。二面體群是“最少的非阿貝爾非阿貝爾群”還有一些技術原因，但我認為這不會以一種已知的方式影響所產生的隱藏子群問題。粗略地說，阿貝爾/不在這裡有很大的不同，因為傅里葉變換很多更好的阿貝爾群（不僅僅是在量子計算的設置中），量子傅里葉變換是有效解決阿貝爾 HSP 的關鍵。不過，這很快就開始變得相當數學化。

此外，這個普遍的故事可能不是最有說服力的，還有更廣泛的原因。文獻中有各種定理說

（打破某些基於格的密碼學）意味著（某些最壞情況的格問題）的量子算法。

這些最壞情況的格問題很有趣，因為它們似乎有非密碼分析用途（分解主要用於破解密碼學）。例如，最接近向量問題的有效解決方案意味著針對加性高斯白雜訊通道的（接近最優）程式碼的最優解碼算法，編碼理論家會對此感到高興。

無論好壞，人們很少參數化他們的密碼系統，以便上述定理成立。例如，我所知道的所有減少都說雜訊與模量比必須很大 $ \Omega(\sqrt{n}) $ ，但人們通常將其設置為某個常數 $ O(1) $ （比如8個什麼的）。不知道這會使經典攻擊變得更好，但這意味著上述定理不成立——打破它的量子電腦不再需要讓編碼理論家高興。

此外，LWE 的某些（相當奇怪的）實例確實承認了非平凡的量子算法。還存在已經陷入量子攻擊的基於格的密碼系統（使用非標準的底層問題）（這裡總結）。

對於從事量子算法工作的人來說，回答這個問題會很棒，但對於那些不從事格子加密工作的人，我會將事情總結為

1. LWE （似乎）很難，因為一段時間以來沒有人為此提供算法，儘管來自編碼理論社區（當然還有密碼分析家）的自然動機
2. 將目前技術擴展到 LWE 存在天然障礙，因為它對應於隱藏子群問題的非阿貝爾實例，而指數加速（大部分）僅限於HSP 的阿貝爾實例。
3. 我們獲得非平凡的量子加速的計算問題列表實際上比大多數人想像的要短得多（尤其是在閱讀了 Grovers 之後，這是一種廣泛的技術，但除了設置參數之外在密碼學上不是一個問題）。

話雖這麼說，如果有人放棄了 LWE 實例的 BQP 算法，這些實例沒有被最壞情況到平均情況的減少所覆蓋，但被用於密碼學（低雜訊率），它會

1. 打破大量現有的基於格的加密方案，以及
2. 不一定會動搖對（正確參數化的）LWE 的量子硬度的信心（因為它不會與量子電腦難以解決的潛在最壞情況晶格問題相矛盾）。

誰知道這種可能性有多大。不過，這將使各種郵件列表在數年內變得更加令人興奮:)

引用自：https://crypto.stackexchange.com/questions/50856