未來是基於安全格的密碼學嗎？

格密碼學是一種後量子密碼學，適用於以下兩個 NP 難題：

1. 從原點找到最短的非零向量
2. 求任意點與原點的晶格外的最小距離。

目前，格密碼系統被 300 維的密鑰空間破壞。另一方面，我們在該密碼系統中使用 400 維。我們將來可以使用這個密碼系統嗎？

我們如何區分這種密碼系統與其他密碼系統？

隨著數學和計算的進步，為了保護系統，我們應該增加密鑰大小。我們知道，對於基於格的系統（例如 NTRU），推薦的密鑰大小約為 $ 3slog(s)+1000 $ 位，其中 $ s $ 是所需的安全級別。今天 $ s=80 $ ，但隨著數學的進步， $ s $ 在增加。 $ s=96 $ 被認為可以提供保護，直到 $ 2020 $ . 因此，如果我們將來使用 lattice，我們應該增加它的維度。

有關其他加密方案複雜性的更多詳細資訊，您可以查看“基於同源的加密方案”和“關於算法和密鑰大小的年度報告”。

最近，Lior Eldar 和 Peter Shor 發布了一個 arXiv 預印本，聲稱一個重磅炸彈的結果：即求解LWE的多項式時間量子算法。不幸的是，Oded Regev 發現了算法中的一個缺陷。但是，也許它是一個潛在的威脅格問題。需要進一步研究。

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