科普漫谈 | 初探格理论（下）

在上一篇文章中，我们对格理论所涉及的数学基础做了一个简单的归纳。本篇科普文章将继续带来有关格理论的介绍。

在上一篇的科普文章中，我们简单介绍了向量空间的相关知识，向量空间中的元素满足加法和数乘。对于一般的向量空间而言，这里的数域没有限制，我们一般取实数域。

那什么是格呢？

01

什么是格

相信一听到这个问题，大家的脑海中马上浮现出的就是一个个排列整齐的晶格。

其实从直观上讲，格的物理意义也确实是高维空间中排列规律的点阵。

格的概念与向量空间十分类似，不过这里对数域进行了一个小小的限制，也就是格中的向量只能与整数做数量乘法。

当我们不断变动向量前系数的值，所形成的新向量就不能组成一个连续的向量空间了。因此格中的向量是呈离散排列的，进而解释了为什么在物理意义上格可用晶格形象代表的原因。

二维整数格

如上图所示，其中的每一个点都代表一个由基向量通过线性组合所形成的向量。

下面，我们给出格的数学定义：

给定一组线性无关的向量    ，对整数集中任意  ，则格  可由  的整系数线性组合生成，定义为 并称  为格  的基。

02

格上的困难问题

正因为格的离散性，并且只允许整数出现，我们能够发现很多有趣的问题。

和向量空间一样，格的基也不是唯一的。以下述二维格为例，白色的基向量和蓝色的基向量均可看作二维格的一组基。

从下图我们也可以看到，即使定义了同一个格的两组基，基的长度相差也可能很大，如何找到一组长度最短的基，被普遍认为是困难的，这个问题称作最短独立向量问题（SIVP）。

二维整数格的两组基

除此之外，还有一些其他的基于格上的困难问题，如CVP、BDD等。在实际应用中，基于格设计出的格密码算法，其安全性更多的依赖于容错学习(LWE)困难问题。

何为LWE困难问题呢？

对线性代数有过基本了解的人应该知道，我们可以通过高斯消元法求解矩阵形式的线性方程组问题 
得到的向量  必然满足  。

现在，我们增加一些难度，给定矩阵  和向量  。其中，  为一个随机噪声向量，这时能否通过高斯消除法解出向量  呢？答案是否定的。

因为我们对每行进行消除时，同时会带着噪声进去，导致无法解出任意一个未知数的值。

似乎能想到的办法只有猜测  的值，逐渐逼近  。这样做的复杂度（指数级）是很高的，因此我们称为Learning With Error（LWE）困难问题。

03

格理论有哪些应用

格理论作为用作解决各种问题的算法工具，已经成为一个热门研究课题。它在密码系统和密码分析方面有许多应用。

同态加密的一些著名的构造方法都是基于格的。基于格中点阵，我们能够实现两组向量的映射。如果我们将密文看作向量  ，明文看作向量  的话，这与同态加密的基本思想是一致的。由于（环）LWE加密本身就具有同态性，这也是为什么格上能够构造同态加密的原因。

除此之外，格还可被用来抵御量子计算机的攻击，具有极高的研究价值。

—END—

  文案 | 刘晨      图片 | 杨雅清

本文为同态科技整理

转载需授权，并保留出处

推荐阅读