然而，对付暗码学来说，它需要坚苦问题是成立在平均环境下的，因为这样才气使得密钥随机选取后，所对应的暗码函数不能被破解的概率为高概率。
这句话有些人读了之后就晕了。何谓最坏环境下的坚苦问题？最坏环境下与平均环境下哪个坚苦？
因此，这是格暗码具有吸引力的重要原因之一。（尚有一个吸引力是抗量子，今后再说）
下面我们延伸一下，说明一下随机实例与安详性之间的干系。这里就需要提到NP完全问题。
最坏环境下的坚苦性的优势
逾越“随机实例”的问题，需要对理论计较机科学举办一些深入而美妙的研究。从Ajtai的开创性事情开始，发明白加密算法，个中安详性假设是“最坏环境”（更安详）的假设，而不是随机环境。不幸的是，最坏环境的假设是针对未知的NP完全问题，而且一些理论证据表白无法使它们适应NP完全问题。
可是在最坏环境坚苦性假设下，对漫衍没有任何要求，可以完全制止这个问题。譬喻在格的最坏环境坚苦问题假设下，暗码学算法可以输入任何漫衍的格。
可是在平均环境坚苦性假设下结构暗码学方案有个特点，必需要找到符合漫衍的问题实例。譬喻，基于大整数解析的暗码学结构，它的假设是在某个特定公道漫衍下解析整数是坚苦的。不是对任何漫衍的整数其解析都是坚苦的。譬喻那些具有小因子的数是容易解析的，所以我们选择的时候是要制止的。
定理：假设不存在用于求解某些问题X的随机实例的多项式时间算法，则该加密方案是可证明的安详性。
留意上面的“任意”两个字，说明Ajtai在随机环境与最坏环境两者之间成立起了一个桥梁。
最坏环境意味着任意实例，而平均环境意味着随机实例。然而，，没有加密方案有这种证明。假如您查察文献，除了少少数破例。安详性定理如下所示：
随机实例与可证明的安详性
上一期给各人先容了格暗码，许多伴侣狐疑于格的最坏环境下的坚苦性。这里向各人一一解惑。
问题来了，哪一种好呢？
暗码算法是成立在坚苦问题之上的。前面我们说了，格暗码是成立在最坏环境下的格上尺度坚苦问题之上。而平均环境下的坚苦问题就纷歧样了。它在某些参数下是坚苦的，可是在某些参数下并不坚苦。譬喻，大整数解析问题，这个问题是有前提的，选取的数一方面要足够大，并且要具有素数因子才行。不然压根构不成坚苦问题。
简朴的说，Ajtai成立的归约就是：给定安详参数n（格的维数），在随机环境下假如存在可以或许冲破格暗码系统的对手，则对输入的任意n维格都存在一个解。
假如一个问题成立在最坏环境下的坚苦问题之上，则对付该问题的任何实例都是坚苦的。
Ajtai的开创性归约
在格暗码之前，人们还没有发明有可以或许成立在最坏环境下的坚苦问题。1996年Ajtai开创性的将格暗码成立在“最坏环境”（更安详）的安详性假设之上，而不是随机环境。
最坏环境下与平均环境下哪个坚苦？
在表明之前我直接给出功效：最坏环境下的坚苦性是最最最….坚苦的。
对付暗码学算法而言，虽然是假如可以或许成立在最坏环境下的坚苦性之上是最好了。这样意味着任何环境下都是坚苦的。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
