Lattice Crypto 最壞情況到平均情況
我目前正在閱讀 ETSI 白皮書Quantum Safe Cryptography and Security
在第 24 頁上可以找到以下語句：
格問題還受益於所謂的最壞情況到平均情況減少，這意味著在設置基於格的密碼系統的任何參數時，所有密鑰在最簡單情況下與在最壞情況下一樣難以破解。在像 RSA 這樣的加密系統中，生成密鑰涉及選擇兩個非常大的隨機數，它們應該是素數並且應該產生分解問題的硬實例，但是存在一定程度的選擇錯誤並導致安全級別較弱的機率. 在基於格的密碼學中，所有可能的密鑰選擇都是強大且難以解決的。
這讓我感到困惑，因為我對格子中最壞情況和平均情況的減少有不同的理解。根據我的理解，它的含義如下：
平均而言，格密碼系統（即隨機選擇的密鑰）與底層格問題中最難的問題一樣難。這並不意味著所有可能的鍵選擇都很強且難以解決。
現在，誰錯了？我還是 ETSI？
你說的對。在問題 Q 的實例上，從問題 P 到分佈 D 的最壞情況到平均情況的減少大致意味著
$$ \Pr_{q\leftarrow D(Q)}[q\text{ is hard} ~|~ \exists~\text{any instance of P that is hard}]>1-\text{negligible}. $$因此，即使分佈 D 的支持是問題 Q 的整個實例集，這當然並不意味著問題 Q 的每個實例都是困難的。 順便說一句，應該指出，為晶格問題設置參數的方式不會導致從最壞情況到平均情況的特別有意義的歸約，因為歸約並不嚴格——問題中格的維度P 小於問題 Q。
儘管如此，進行這種縮減的最大效用在於，正是這種縮減導致人們遇到了（環/模組）-SIS 和（環/模組）-LWE 的問題，以及這些問題實例（均勻）的分佈目前用於實際的格密碼學。分析這些問題的隨機實例的難度成為一個獨立的問題。