陈智罡

对于密码学来说，它所需要困难问题是要建立在平均情况下的，因为这样才能使得密钥随机选取后，所对应的密码函数不能被破解的概率为高概率。但是在平均情况困难性假设下构造密码学方案有个特点，必须要找到合适分布的问题实例。例如，基于整数分解的密码学构造，它的假设是在某个特定合理分布下分解整数是困难的。不是对任何数其分解都是困难的。例如那些具有小因子的数是容易分解的，所以我们选择的时候是要避免的。

但是在最坏情况困难性假设下，对分布没有任何要求，可以完全避免这个问题。例如在格的最坏情况困难问题假设下，密码学方案可以输入任何分布的格。为什么呢？首先说说何谓最坏情况。

最坏情况下是困难的，就是说它的困难性是最困难的，因为在最坏情况下所花费的时间是最多的。例如我说攻击这个城堡，平均情况下3天可以拿下，但是最坏情况下需要7天。显然最坏情况下所花费的代价最大。如果在最坏情况困难性的假设下，即使以小概率攻破了该困难问题，则意味着攻破了所有基于该困难问题的实例。所以不会产生像平均困难性假设下的那样的问题，例如：对于某些分布是容易的。这使得在最坏情况困难性假设下构造密码学方案非常有吸引力。密码学参数也更加直接。

另外平均情况下是困难的，则最坏情况下一定是困难的。反之未必。

注意，密码学方案是要建立在平均情况困难问题假设下的。只有这样，在随机选取密钥下，我们的密码学方案才能以高概率不被破解。格归约理论的出现，把最坏情况与平均情况建立了连接，使得我们可以在平均情况的问题下建立密码学方案，但是其安全性建立在最坏情况下。