格（Lattice）学习笔记之三：对偶格

Original 东泽安比技术社区 2020-07-28 12:30

本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。

对偶格（Dual Lattice）

线性空间里面一个很重要的概念就是对偶空间（Dual Space）。一个线性空间的对偶空间就包括了所有从的线性变换函数。

同理可得，一个Lattice也有它对应的对偶空间，即这个空间中的每一个元素都是一个把这个格中的元素映射到整数空间中的线性变换。一般来说我们可以用一个向量来表达线性变换，所以也就是说一个Lattice的对偶空间就是一组向量，而这些向量乘以格中的任意格点，都可以得到一个中的元素。

再换句话来说，也就是说这些对偶的向量，乘以任意Lattice中的格点向量，都能得到一个整数。这些向量本身就组成了另一个Lattice，我们把这个新的Lattice成为对偶格（Dual Lattice）。

系统性的定义的话，一个Lattice 的对偶格就是一组向量并且满足：

我们拿最常见的笛卡尔整数格举个例子。

由于中的每个格点对应的向量都是整数，所以任何整数向量和它的乘积也都是整数，即：

我们在上面的图中可以看出，这个格与它的对偶格是一样的，所以格点都重合了。

如果我们给原来的格叠加了一个线性变换（这里是旋转），那么新的Lattice 的对偶格可以通过旋转变换原本的对偶格来得到。

这个原因也很简单，假如我们拥有在中的格点与对偶格点，和一组在中的。已知了是旋转了得到的。因为旋转一对向量并不会改变向量之间的乘积，所以我们只需要对应的旋转，即，就能保证乘积不变，也能得到整数。

同理可得，如果我们缩放了一个Lattice ，使得它的格点扩大/缩小了倍的话，为了保证点乘的乘积相同，最后得到的对偶格的大小就要对应的变成倍。

仔细观察可以发现，不管是什么样的Lattice，格和对偶格之间有一些基本的关系：

我们可以把对偶格理解成是一个格的“倒数”，因为很多时候它们之间的关系是反过来的。

在笛卡尔整数格中，对偶格看起来很好理解，因为和原本的格长得也差不多。但是实际上对偶格和格本身其实并没有太大的几何上的关联，我们最好把对偶格里面的每一个向量理解成一个“线性变换函数“，而不是一个几何上的格点。

比如说上图中这个斜过来的格，它的对偶格就和本身没有任何几何上的关联。

Lattice分层

当我们得到了一个Lattice 的对偶格之后，我们可以做一件很有趣的事情：给原有的Lattice分层。

我们知道对偶格中的每一个格点都可以和原本的格中的任何格点相乘并且得到一个整数。我们可以选定一个对偶格中的点，然后让原本的格中的所有点都和这个点相乘。最后我们观察所有的乘积结果的大小，并且把所有得到相同结果的格点都分为“一层”。

接着，如果我们再选取另一个对偶格中的点，然后又可以得到另一组不一样的分层。

我们观察会发现，这个分层的密度和层与层之间的距离都不一样。这个距离，其实是与选取的对偶格中的向量的长度成反比的。

这代表了什么呢？我们可以用对偶格向量的长度来逼近原本的这个格的覆盖半径！

我们知道，所有的中的格点都只能在每一层上面，所以层与层之间的缝隙里是不会有任何格点的。同理我们就可以塞一个圆进去，而这个圆的半径一定得小于等于整个格的覆盖半径。

这是因为，覆盖半径是在空间中任意选取一个点，这个点到附近的格点的最远距离。因为我们知道了对偶格点构成的分层之间的距离，所以覆盖半径肯定要大于等于这个距离。

这也就是说，我们可以在这个对偶格中任意选择一个点，然后找到对应的分层距离，就可以逼近原本的格的最大半径了。因为选择的的长度越短，我们得到的分层距离越大，所以理论上这个对偶格的最短向量构成的分层距离，就是我们能逼近的最大上限了。这也就是说，如果比较短的话，那么对应的也会比较大。反之也是如此。

Banaszczyk定理

我们之前观察到的Lattice的覆盖半径的大小与对偶格的最短向量长度的反比例关系，被Banaszczyk总结成了定理。首先，对于任何的Lattice ：

这一点规定了覆盖半径与对偶格最短向量这两个值之间的乘积一定会在一个上限的范围内。同时，我们不仅可以对应最短的向量与最大的覆盖半径，我们还可以对应其他的短向量：

这也就是说，我们可以把一个格中的最短向量和它的对偶格中的最短向量一一对应起来，找到它们之间的关系。如果我们要找一个格的最短向量，我们不妨先找到对偶格的覆盖半径，然后再根据上面的关系式来逼近我们想要的结果。1

BDD问题规约到SIVP

学习完对偶格（Dual Lattice）的概念之后，我们就可以把上一篇笔记中看过的BDD问题，即至多只有一个解，并且搜索的半径小于的CVP问题，规约到SIVP问题上来。

首先，假设我们在一个格中，给定一个中的随机点，然后求解BDD。

我们第一步可以做的是，先找到这个格的对偶格，并且在这个对偶格中求解SIVP问题，得到对应的一组最短向量。

得到这一组最短向量之后，我们依次选择其中的每一个向量，然后根据这个向量对于格进行分层，然后找到距离最近的一层。上图展示了第一个向量得到的分层。

当我们重复这个操作次之后，就会得到个不同的分层。这个时候我们就可以把这些分层的交汇点拿到，这就是BDD问题的解了。这是因为SIVP的解拿给我们的都是线性独立的向量，所以我们根据这个向量构成的维的hyperplane分层之间也是相互独立的，这些平面也会相聚在一个点上。

这个依靠SIVP的算法基本上可以解决大部分BDD问题。但是为了确保我们输出的结果是BDD问题的正确解，我们还需要额外的加上一个约束：

我们需要规定这个BDD问题给定的向量需要距离最近的格点在的范围之内的时候，这个方法就可以找到正确的解。这个不等式的后半部分可以根据上面的Banaszczyk定理得到。

这一约束，对于BDD问题原本的定义要限制多了不少，但是已经是一个很强大的算法了。1

Lattice中的模（Modulo a Lattice）

另一个对于对偶格的用处，在于Lattice的模运算。

我们知道一个Lattice 是一组在中离散的格点。这些格点之间可以相加，并且最后还是会得到中的格点。因为拥有这一特性，被称为的一个Additive Subgroup（加法子群？）。

因为这一特性，根据群理论，我们可以构成一个Quotient Group（商群？），即。

这个概念看起来比较烧脑，其实理解起来很简单。就像我们平时一样，我们可以把整个多维空间用这个Lattice的Determinant组成的多面体平分成多份。如果我们仔细观察上面图中的阴影部分上覆盖的格点，会发现这上面的格点的分布规则和隔壁每一个一样的多面体上面的分布是一模一样的。

这也就是说我们可以把任何一个空间中的点使用格求模的方法，压缩到这么大的范围中，并且这就足够表示这个点在空间中距离其他的格点的位置了。

同理可得，如果我们观察上图下方组成的基形成的阴影部分，即Determinant组成的空间，我们会发现这一部分也可以很好的切割整个的空间，所以我们也可以基于这一组基进行求模。

在这个Quotient Group中的一个向量，我们可以用来表示。

对于这个向量，我们其实还有另外一种表达方式：

这个向量可以用对偶格的基向量乘上得到的一个数字，然后取小数点部分来表示。注意这里因为并不在格点上，所以对偶空间基向量乘上它不会得到整数。这个小数点后面的部分，就可以独立的代表这个Quotient Group中的每一个元素。这算是一个把群元素映射到上的一种小技巧。

封面图来自unsplash，作者CardMapr

往期回顾

格（Lattice）学习笔记之一：历史与基本概念

格（Lattice）学习笔记之二：计算问题

初探全同态加密：FHE的定义与历史回顾

初探全同态加密之二：格密码学与LWE问题

初探全同态加密之三：构建GSW全同态加密系统

浅谈零知识证明之一：背景与起源

浅谈零知识证明之二：简短无交互证明（SNARK）

浅谈零知识证明之三：zkSNARK证明体系的实现（上）

浅谈零知识证明之四：zkSNARK证明体系的实现（下）

密码学学习笔记——Sigma Protocol

密码学学习笔记——aSCV

探索零知识证明系列（一）：初识「零知识」与「证明」

探索零知识证明系列（二）：从「模拟」理解零知识证明

探索零知识证明系列（三）：读心术：从零知识证明中提取「知识」

探索零知识证明系列（四）：亚瑟王的「随机」挑战：从交互到非交互式零知识证明

探索零知识证明系列（五）：云中「秘密」：构建非交互式零知识证明

zkPoD:区块链，零知识证明与形式化验证，实现无中介、零信任的公平交易

PoD-Tiny——实现零信任交易的最简协议

如果量子计算时代到来，我们的比特币安全吗？

零知识证明学习资源汇总

从零开始学习 zk-SNARK（一）——多项式的性质与证明

从零开始学习 zk-SNARK（二）——多项式的非交互式零知识证明

从零开始学习 zk-SNARK（三）——从程序到多项式的构造

从零开始学习 zk-SNARK（四）——多项式的约束

从零开始学习 zk-SNARK（五）—— Pinocchio 协议

零知识证明 Learn by Coding：libsnark 入门篇

链上富人寻「隐私」记（一：Mixer 篇）

理解零知识证明算法Bulletproofs（一）：Range Proof

理解零知识证明算法Bulletproofs（二）：Improved Range Proof

理解零知识证明算法Bulletproofs（三）：Range Proof 实现分析

理解零知识证明算法Bulletproofs（四）：Arithmetic Circuits

以太坊颠覆了以太坊：引入密码学实现2.0性能突破

长按二维码添加微信进群技术讨论

邮箱 : info@secbit.io

收录于合集 #格（Lattice）学习笔记

14个

上一篇格（Lattice）学习笔记之二：计算问题下一篇格（Lattice）学习笔记之四：SIS与LWE 问题

Scan to Follow