Post-Quantum-Cryptography
為什麼密碼學中只使用格問題？
那裡有成千上萬個 NP 難題。為什麼只有格問題應用於密碼學？
使問題適合密碼學的因素與使問題 NP-hard 的因素略有不同。
密碼學需要的是平均情況硬度——即，隨機選擇的問題實例對於對手來說應該是“難以解決的”。然而，一些 NP-hard 問題（例如 3SAT）的隨機實例被證明是容易的且機率很高。
格很有趣，因為它的一些平均情況下的難題（例如最短整數解，SIS）允許減少最壞情況下的難題（例如最短獨立向量問題，SIVP）——即解決一個隨機實例問題就像解決另一個問題的最壞情況一樣困難。也沒有針對這些問題的有效量子算法。
此外，格有足夠的底層代數結構，允許基於這些難題建構密碼原語（OWF、Trapdoors、FHE……）——參見 Peikert 的調查。
看
- 1：堆棧溢出
- 2：cs.stackexchange，
- 3：關於基於 P!=NP和假設的密碼學的可能性
- （在 Ajtai 之前）4：A Personal View of Average-Case Complexity（Impagliazzo 1995）。
- 5：平均案例複雜度（Trevisan，Bogdanov）
似乎這是一個懸而未決的問題：“如果我們可以將密碼學建立在 $ P\not= NP $ ”。此外，正如之前的海報所寫，除了格之外還有其他一些問題：多元密碼（J.Patarin 方案）和基於程式碼的問題（McEliece 密碼系統）。