假如我们能找到格的正交基，这个问题就变得容易解了。可是不幸的是，很容易证明大大都格不具有正交基。可是，可以界说一个基险些正交的暗示法，这对我们长短常有用的。此刻，我们可以界说一个好的基：一个由相对较短的近正交向量构成的基。计较这样好的基就是台甫鼎鼎的格基归约算法的目标（譬喻著名的LLL和BKZ算法）。
到今朝为止，我们所接头的问题还不容易用于结构暗码协议。然而，在1996年Ajtai开创性的论文“Generating hard instances of lattice problems”中，Ajtai引入了短整数解格中的第二个根基问题是最近向量问题（CVP）。在这个问题中，给定了由某种基界说的格以及该格地址向量空间中的方针向量，任务是确定格中最靠近方针向量的向量。
事实已经证明，LWE和SIS问题都可以简化为已研究多年的格上的尺度坚苦问题，这为基于格的暗码学提供了坚硬的安详基本。可是在实际应用中，人们凡是利用那些无法担保安详归约的参数，譬喻噪声漫衍太窄可能LWE漫衍中的奥秘是从极小子会合提取的。另外，，为了提高效率，凡是利用环LWE版本。
给定一个参数β和一个格的基，我们需要给出判定格是否包括长度最大为1的非零向量，可能最短的非零向量的长度是否大于β。假设这两种环境之一是正确的。
格上的暗码问题
上期我们先容了格上著名的坚苦问题：SVP（最短向量）问题。该问题是计较问题，而暗码界更感乐趣的是鉴定问题。将SVP（最短向量）问题转化为鉴定性问题就引出著名的GapSVP问题。
要相识有关办理格问题的最著名要领的更多信息，我们推荐Nguyen, P. Q. and Vallée, B. “The LLL Algorithm: Survey and Applications”. Springer Berlin Heidelberg, 2010。对付LWE和SIS问题及其在暗码学中的应用，我们推荐Peikert的论文“A Decade of Lattice Cryptography”. Foundations and Trends® in Theoretical Computer Science, 10(4), pp 283-424，2016。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
