問題來了，哪一種好呢？
最壞情況下的困難性的優勢
對於密碼學演算法而言，當然是如果能夠建立在最壞情況下的困難性之上是最好了。這樣意味著任何情況下都是困難的。
然而，對於密碼學來說，它需要困難問題是建立在平均情況下的，因為這樣才能使得金鑰隨機選取後，所對應的密碼函式不能被破解的概率為高概率。
但是在平均情況困難性假設下構造密碼學方案有個特點，必須要找到合適分佈的問題例項。例如，基於大整數分解的密碼學構造，它的假設是在某個特定合理分佈下分解整數是困難的。不是對任何分佈的整數其分解都是困難的。例如那些具有小因子的數是容易分解的，所以我們選擇的時候是要避免的。
但是在最壞情況困難性假設下，對分佈沒有任何要求，可以完全避免這個問題。例如在格的最壞情況困難問題假設下，密碼學演算法可以輸入任何分佈的格。
因此，這是格密碼具有吸引力的重要原因之一。（還有一個吸引力是抗量子，以後再說）
Ajtai的開創性歸約
在格密碼之前，人們還沒有發現有能夠建立在最壞情況下的困難問題。1996年Ajtai開創性的將格密碼建立在“最壞情況”（更安全）的安全性假設之上，而不是隨機情況。
簡單的說，Ajtai建立的歸約就是：給定安全引數n（格的維數），在隨機情況下如果存在能夠打破格密碼系統的敵手，則對輸入的任意n維格都存在一個解。
注意上面的“任意”兩個字，說明Ajtai在隨機情況與最壞情況兩者之間建立起了一個橋樑。
下面我們延伸一下，說明一下隨機例項與安全性之間的關係。這裡就需要提到NP完全問題。
隨機例項與可證明的安全性
一般來說，我們假設不存在總能解決NP完全問題的演算法。這是一個非常安全的假設，因為對於演算法而言，這確實是一件很難的事情。但是提出一種演算法來解決隨機問題的可能性似乎要容易得多。
然而，沒有加密方案有這種證明。如果您檢視文獻，除了極少數例外。安全性定理如下所示：
定理：假設不存在用於求解某些問題X的隨機例項的多項式時間演算法，則該加密方案是可證明的安全性。
注意“隨機例項”。舉一個具體的例子，我們可能假設不存在用於以一定的概率將兩個隨機n位素數的乘積分解為因子的多項式時間演算法。這與假設不存在用於始終分解兩個隨機n位素數的所有乘積的多項式時間演算法完全不同（不太安全）。
超越“隨機例項”的問題，需要對理論電腦科學進行一些深入而優美的研究。從Ajtai的開創性工作開始，發現了加密演算法，其中安全性假設是“最壞情況”（更安全）的假設，而不是隨機情況。不幸的是，最壞情況的假設是針對未知的NP完全問題，並且一些理論證據表明無法使它們適應NP完全問題。
