格上构建密码学方案的吸引力:最坏情况困难性与平均情况困难性的连接，Ajtai,96

 而密码学中的困难性需要的是：平均情况下的困难性。例如，如果随机选择的key，没有概率多项式时间的算法能够以不可忽略的概率破解该key。

 而计算复杂论中的困难性是：最坏情况下的困难性。例如，没有多项式时间算法能够解决该问题的所有实例。即，任何多项式时间算法，存在某个实例无法解决。这对密码学是不够的：存在某个key其破解是困难的。即使不可忽略的很小一部分key能被破解，该方案也被认为是不安全的。

 密码学函数的构造要求：在最坏情况下的标准计算复杂度假设下，密码学函数在平均情况下是可证明困难的。然而，对于目前的一些密码学方案，不仅要要在最坏情况下假设其困难，而且要在平均情况下假设其困难。例如，基于大整数分解的密码学方案。

 最坏情况困难性与平均情况困难性的连接，Ajtai,96。说的是：对任何格及某个近似因子，如果没有算法能够解决近似SVP问题，则从一个特定的容易选取的分布中随机选取格时，SVP问题是困难的。而这里最重要的是发现了一个随机格（q元格），从随机格里选取的格，其上的格上标准困难问题例如SVP是困难的。