深度详谈 | 格理论进阶之格困难问题

在之前的文章中，我们介绍了格理论的相关概念。其实格中还有许多的困难问题以及求解算法等都是很值得探讨的，本篇将对这些问题做一个简单总结。

01

格密码算法

搞懂格密码算法还要从量子计算机开始说起。

1.

起因——量子计算机的威胁

1994 年，Peter Shor 提出了Shor 算法，主要想表达的是可以用量子计算机在多项式时间内求解周期函数的周期。而大家所熟知的密码算法RSA 和椭圆曲线所基于的困难问题“大整数分解”和“离散对数求解”都可以转化为周期函数求解周期的问题。

也就是说，量子计算机可以求解这些困难问题，从而攻击密码算法。

那么，随着量子计算机的发展落地，许多密码算法将不再安全。

2.

推动——后量子密码

针对这种威胁，密码学家们提出了“后量子密码”这一概念，也就是抵抗量子计算机对现有密码算法攻击的新一代密码算法。

在美国国家标准局NIST 第三轮入选的七个密码算法中，四个为公钥加密算法，分别为Classic McElience, CRTSYALS-KYBER, NTRU 和SABER，三个数字签名算法，分别为CRYSTAKS-DILITHIUM，FALCON 和Rainbow。其中公钥加密中CRYSTALS-KYBER、NTRU 和SABER 和数字签名方案中CRYSTALS-DILITHIUM 和FALCON 均基于格的方案，其中五个基于格密码的算法分别基于Module-LWE, SVP, Module-LWR, NTRU 和SIS 困难问题进行构造。

以上这5 个格密码算法，目前被认为是安全的后量子密码。而这些格密码算法的安全性依赖于求解格中问题的困难性，格中问题越难，对应的格密码算法就越安全。

在上一篇文章中，我们介绍了格中的一个困难问题LWE。

其实，格中有许多困难问题，而这些困难问题间又可以互相规约，它们的困难程度、规约关系、还有求解算法等都是很值得探讨的。

02

格中基础的困难问题

接下来，我们先介绍格中四种基础的困难问题——SVP、CVP、SIS，BDD。

1.

最短向量问题SVP

给定任意一组基  ，生成格  ，找到格  上最短非零向量，即找到向量  使得对于任意其他非零向量  ,  ，最短向量  的长度记作  。

SVP

2.

最近向量问题CVP

给定格基  并以该格基生成  维格  ，给定一目标向量  ，试找到格  上最接近  的向量  ，使得对于任意其他向量  ，  。

CVP

3.

短整数解问题SIS

给定  个均匀随机分布的向量  ，按列构成矩阵  ，试找到一非零短整数向量解  使得  且 mod  。

SIS

4.

有限距离编码问题BDD

给定一组基  和它构成  维格  和目标向量  ，且目标向量  到格  上任意格点的最短距离满足条件  ，试找到格  上的唯一向量  使得  。

BDD

以上4 种困难问题，是格中比较基础的。对于入选NIST 的5 种算法所基于的困难问题，如Moudle-LWE、Moudle-LWR，这些困难问题的定义会稍稍复杂一些，涉及到抽象代数中的分圆多项式等，在下一篇文章中将单独来讲。

—END—

  文案 | 季炜丹      排版 | 刘晨

本文为同态科技整理

转载需授权，并保留出处

推荐阅读