格密码学简介(第2部分)

上期我们介绍了格上著名的困难问题:SVP(最短向量)问题。该问题是计算问题,而密码界更感兴趣的是判定问题。将SVP(最短向量)问题转化为判定性问题就引出著名的GapSVP问题。

给定一个参数β和一个格的基,我们需要给出判断格是否包含长度最大为1的非零向量,或者最短的非零向量的长度是否大于β。假设这两种情况之一是正确的。

格中的第二个基本问题是最近向量问题(CVP)。在这个问题中,给定了由某种基定义的格以及该格所在向量空间中的目标向量,任务是确定格中最接近目标向量的向量。

如果我们能找到格的正交基,这个问题就变得容易解了。但是不幸的是,很容易证明大多数格不具有正交基。但是,可以定义一个基几乎正交的表示法,这对我们是非常有用的。现在,我们可以定义一个好的基:一个由相对较短的近正交向量组成的基。计算这样好的基就是大名鼎鼎的格基归约算法的目的(例如著名的LLL和BKZ算法)。

格上的密码问题

到目前为止,我们所讨论的问题还不容易用于构造密码协议。然而,在1996年Ajtai开创性的论文“Generating hard instances of lattice problems”中,Ajtai引入了短整数解

事实已经证明,LWE和SIS问题都可以简化为已研究多年的格上的标准困难问题,这为基于格的密码学提供了坚实的安全基础。但是在实际应用中,人们通常使用那些无法保证安全归约的参数,例如噪声分布太窄或者LWE分布中的秘密是从极小子集中提取的。此外,为了提高效率,通常使用环LWE版本。

要了解有关解决格问题的最著名方法的更多信息,我们推荐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。

根据国家《 关于防范代币发行融资风险的公告 》,大家应警惕代币发行融资与交易的风险隐患。

本文来自 LIANYI 转载,不代表链一财经立场,转载请联系原作者。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章