Provable-Security
在基於格的密碼學中，“最壞情況硬度”是什麼意思？
在基於格的密碼學的維基頁面中，“最壞情況硬度”定義如下：
格問題的最壞情況硬度意味著破解密碼結構（即使具有一些不可忽略的小機率）至少與在最壞情況下解決幾個格問題（近似地，在多項式因子內）一樣難。換句話說，破解密碼結構意味著一種有效的算法來解決一些潛在的格問題的任何實例。
但是，基於格的密碼學中的“最壞情況硬度”和基於離散對數的標準密碼學中的“平均情況硬度”之間有什麼區別，比如ElGamal 加密？
這似乎令人困惑。例如，闖入 ElGamal Encryption 也導致破壞其他幾個密碼結構並解決眾所周知的數論難題：計算 Diffie-Hellman。但是，這並不認為是“最壞情況下的硬度”。
一行：最差意味著任何，平均意味著隨機。
基於格的密碼系統
讓我重述一遍。修復安全參數 $ n $ . 減少表明存在輸入任何晶格問題的求解器 $ n $ 維格使用攻擊者破解具有安全參數的基於格的密碼系統 $ n $ 在平均情況下。
由於我們可以解決任何實例，我們可以解決最難的維度 $ n $ .
ElGamal 加密 - 平均情況
我們有一個減少，將 CDH/DDH 問題的隨機實例轉換為單向性/不可區分性博弈的*隨機問題。*這意味著安全性基於問題的平均案例難度。
ElGamal 加密 - 最壞情況
正確地說，El Gamal 加密方案的安全性可以基於組上的類 DL 問題的最壞情況硬度而不是安全參數。
修復一個素數組。我們可以將組中的任何DL/CDH/DDH 問題實例轉換為同一組中問題的隨機實例。（這個性質被稱為隨機自約化。）結合前面的約化，我們可以說安全性是基於固定組上問題的最壞情況硬度。