CVP与对偶格 在开始详细学习SIS之前，不妨再来重新回顾一下CVP问题。 我们知道，CVP问题就是给定一个任意的点$ \mathbf{t} \in \mathbb{R}^n $，和一个Lattice $ \Lambda $，找到一个在$ \lvert \lvert \mathbf{e} \rvert \rvert $范围内的格点$ \mathbf{v} \in \Lambda $。我们也可以使用格点向量$ \mathbf{v} $与误差向量$ \mathbf{e} $的形式来表示我们的目标向量： $$ \mathbf{t = v + e} $$ 我们之前也学过对偶格的定义。假设我们找到了$ \Lambda $的对偶格$ \Lambda^\vee $，并且用$ \mathcal{L}(\mathbf{D}) $来表示。（即$ \mathbf{D} $是对偶格$ \Lambda^\vee $的基向量组成的矩阵。）根据对偶格的定义，对偶格的基向量乘以任何一个$ \Lambda $中的格点都会得到一个整数。所以我们可以观察一下$ \mathbf{D} $与$ \mathbf{t} $的乘积： $$ \begin{align*} s &= \langle \mathbf{D}, \mathbf{t} \rangle \text{ mod }1\ &= \langle \mathbf{D}, \mathbf{v} \rangle + \langle \mathbf{D}, \mathbf{e} \rangle \text{ mod }1\ &= \langle \mathbf{D}, \mathbf{e} \rangle \text{ mod }1 \end{align*} $$ 因为我们知道$ \langle \mathbf{D, v} \rangle $是一个整数，然而$ \mathbf{e} $并不在格上，所以会得到一个$ \mathbb{R} $中的任意小数。最后得到的$ \mathbf{s} $就是表示这个误差特性的一个小数，而且不管$ \mathbf{t} $在什么方位，其实真正决定了$ \mathbf{s} $的值的是误差$ \mathbf{e} $。在译码学中，我们一般把$ \mathbf{s} $这个数值称作伴随式译码（syndrome encoding）。…

q阶随机格（q-ary random lattices） 在密码学的应用中，一般来说我们都会随机选取一个Lattice来做任何数学运算。这个随机的Lattice的每一个格点都应该是在整数格$ \mathbb{Z}^n $中的，这样其中的每一个格点的坐标都是整数。 因为计算机系统的特点，并且也为了方便计算，我们一般都会选择一个比较大的数字$ q $来作为我们所有涉及到的数字的上限。 结合上面两条要求，我们一般在密码学算法中用到的格，都被称作q阶随机格（q-ary random lattice）。一个q阶随机Lattice $ \Lambda $需要满足如下的要求： $$ q\mathbb{Z}^n \subseteq \Lambda \subseteq \mathbb{Z}^n $$ 其中，$ q\mathbb{Z}^n $代表了包含了一个mod q的循环群。这样一来，所有和q阶Lattice有关的计算，都可以通过q模的数学运算来完成。 生成q阶随机格 最常见的生成随机格的方式主要为两种。首先，我们都需要随机的生成一个随机矩阵$ \mathbf{A} \in \mathbb{Z}^{n \times d}_q $。 当我们获得了$ \mathbf{A} $矩阵之后，我们首先可以做的，就是把这个矩阵的每一行作为我们生成的格的基向量，得到第一个Lattice： $$ \Lambda_q(\mathbf{A}) = {\mathbf{x} : \mathbf{x} \text{ mod } q \in \mathbf{A}^T \mathbb{Z}^{n}_q} \subseteq \mathbb{Z}^d $$ 也就是说，我们得到的格$ \Lambda_q $，$ \mathbf{A} $与$ \mathbb{Z}^n_q $中的所有点的线性组合组成的集合。 除此之外，我们还有一种反过来的方式，可以定义另一个随机格：找到所有的向量$ \mathbf{x} $，使得$ \mathbf{Ax} = 0 $。 $$ \Lambda_q^\perp(\mathbf{A}) = {\mathbf{x}: \mathbf{Ax} = 0 \text{ mod } q} \subseteq \mathbb{Z}^d $$ 我们生成的这两个Lattice，即$ \Lambda_q, \Lambda_q^\perp $，都符合我们上一部分提到的这个约束，即$ q\mathbb{Z}^n \subseteq \Lambda \subseteq \mathbb{Z}^n $。并且值得注意的是，我们根据同一个$ \mathbf{A} $生成的两个格是完全不一样的两个系统，几乎所有的格点都大相径庭，但是这两个Lattice之间却又有着很微妙的对偶关系。…

对偶格（Dual Lattice） 线性空间里面一个很重要的概念就是对偶空间（Dual Space）。一个线性空间$ V \in \mathbb{R} $的对偶空间就包括了所有从$ V \rightarrow \mathbb{R} $的线性变换函数。 同理可得，一个Lattice也有它对应的对偶空间，即这个空间中的每一个元素都是一个把这个格中的元素$ \mathbf{v} \in \mathcal{L} \rightarrow \mathbb{Z} $映射到整数空间中的线性变换。一般来说我们可以用一个向量来表达线性变换，所以也就是说一个Lattice的对偶空间就是一组向量，而这些向量乘以格中的任意格点，都可以得到一个$ \mathbb{Z} $中的元素。 再换句话来说，也就是说这些对偶的向量，乘以任意Lattice中的格点向量，都能得到一个整数。这些向量本身就组成了另一个Lattice，我们把这个新的Lattice成为对偶格（Dual Lattice）。 系统性的定义的话，一个Lattice $ \Lambda $的对偶格$ \Lambda^\vee $就是一组向量$ \mathbf{x} \in span(\Lambda) $并且满足： $$ \forall \mathbf{v} \in \Lambda: \langle \mathbf{x}, \mathbf{v} \rangle \in \mathbb{Z} $$ 我们拿最常见的笛卡尔整数格$ \mathbb{Z}^n $举个例子。 由于$ \mathbb{Z}^n $中的每个格点对应的向量都是整数，所以任何整数向量和它的乘积也都是整数，即： $$ (\mathbb{Z}^n)^\vee = \mathbb{Z}^n $$ 我们在上面的图中可以看出，这个格与它的对偶格是一样的，所以格点都重合了。 如果我们给原来的格叠加了一个线性变换$ \mathbf{R} $（这里是旋转），那么新的Lattice $ \mathbf{R}\Lambda $的对偶格可以通过旋转变换原本的对偶格来得到。 $$ (\mathbf{R}\Lambda)^\vee = \mathbf{R}(\Lambda^\vee) $$ 这个原因也很简单，假如我们拥有在$ \Lambda $中的格点与对偶格点$ \mathbf{v, x} $，和一组在$ \mathbf{R}\Lambda $中的$ \mathbf{v’, x’} $。已知了$ \mathbf{v’} $是旋转了$ \mathbf{v} $得到的。因为旋转一对向量并不会改变向量之间的乘积，所以我们只需要对应的旋转$ \mathbf{x} $，即$ \mathbf{Rx} $，就能保证乘积不变，也能得到整数。 $$ \mathbf{v’} = \mathbf{Rv}\ \mathbf{x’} = \mathbf{Rx}\ \langle \mathbf{v, x} \rangle = \langle \mathbf{v’, x’} \rangle $$ 同理可得，如果我们缩放了一个Lattice $ \Lambda $，使得它的格点扩大/缩小了$ q $倍的话，为了保证点乘的乘积相同，最后得到的对偶格的大小就要对应的变成$ q/1 $倍。 $$ (q \cdot \Lambda)^\vee = \frac{1}{q} \cdot \Lambda^\vee $$ 仔细观察可以发现，不管是什么样的Lattice，格和对偶格之间有一些基本的关系： $$ \Lambda_1 \subseteq \Lambda \iff \Lambda_1^\vee \supseteq \Lambda_2^\vee\ (\Lambda^\vee)^\vee = \Lambda $$ 我们可以把对偶格理解成是一个格的“倒数”，因为很多时候它们之间的关系是反过来的。…

SVP问题（Shortest Vector Problem） 一个Lattice中最常见的问题，就是最短向量问题（SVP，Shortest Vector Problem）。问题的定义是这样的：给定一个基为$ \mathbf{B} $的Lattice $ \mathcal{L}(\mathbf{B}) $，找到一个这个基构成的格点$ \mathbf{Bx}: \mathbf{x} $，使得这个点距离0坐标点的距离最近。 $$ \mathbf{Bx}: \mathbf{x} \in \mathbb{Z}^k\ \lvert \lvert \mathbf{Bx} \rvert \rvert \le \lambda_1$$ 观察发现，因为$ \lambda_1 $已经是这个格中点和点之间的最短距离了，所以$ \mathbf{Bx} $距离0点的距离其实也不会小于$ \lambda_1 $，最多是等于罢了。 图中给出了一个比较经典的例子，加入我们拥有一组格的基向量$ \mathbf{B} = [\mathbf{b}_1, \mathbf{b}_2] $，我们可以找到一个点$ \mathbf{Bx} $，即$ 5\mathbf{b}_1 - 2\mathbf{b}_2 $对应的这个点，正好就是这个格的最短向量$ \lambda_1 $。 当然，如果我们拿到的基不是很好，其实计算严格的SVP（即找出$ \lambda_1 $）是一个很难的事情，所以SVP这个问题也有个宽松的版本：$ SVP_\gamma $。 在$ SVP_\gamma $中，问题的设定大致一样，但是唯一不一样的在于，我们找到的点$ \mathbf{Bx} $，并不一定需要恰好是最短向量$ \lambda_1 $，而只要满足小于等于$ \lambda_1 $的一个倍数$ \gamma $就行了。 $$ \mathbf{Bx}: \mathbf{x} \in \mathbb{Z}^k\ \lvert \lvert \mathbf{Bx} \rvert \rvert \le \gamma \lambda_1$$ 图上显示的就是当$ \gamma = 2 $的情况。这个时候我们的$ SVP_\gamma $问题就有很多个解了。…

Lattice的历史 Lattice（格）在很早以前就被各大数学家研究了一遍。代表人物有Lagrange，Gauss和Minkowski等等。最近的几十年内，Lattice在密码学、通讯、密码分析上有了很大的应用价值，是非常火的一个领域。 近代Lattice时间线： 1982：LLL basis reduction theorem 使用Lattice来做Cryptanalysis 1996：Ajtai-Dwork 第一次把Lattice中Average-case与Worst-case的复杂度问题关联起来 提出了使用Lattice构造的One-way Function与CRHF（Collision Resistant Hash Function） 2002：找到了Average-case/worst-case复杂度之间的关系，基于Lattice的协议变得更加高效 2005：Regev提出了LWE，并且发现其量子抵抗性 提出PKE，IBE，ABE，FHE等等的可能性 Lattice是什么 Lattice可以被想象成是一个空间中很多有规律分布的、离散的点。 $ n $维空间中最简单的Lattice就是Integer Lattice（整数格）。整数格中最简单的就是基于笛卡尔坐标系的$ \hat{i}, \hat{j}, … $等基向量组成的空间。 $$ \Lambda = \mathbb{Z}^n$$ 我们可以对此Lattice进行任意的线性变换（Linear Transformation）$ B $，然后可以得到新的Lattice。 $$ \Lambda = B \cdot \mathbb{Z}^n : B \in \mathbb{R}^{d \times n}$$ Lattice与Bases（格与基） 更好的描述一个格的方法是使用基向量。 我们假设一个格拥有基向量$ \mathbf{b}_1, \dots, \mathbf{b}_n $。那么这个Lattice就是它的基向量的任意线性组合的集合，我们也可以把所有基向量组合成矩阵$ \mathbf{B} $来表示。 $$ \mathcal{L} = \sum^n_{i=1} \mathbf{b}_i \cdot \mathbb{Z} = {\mathbf{Bx}: \mathbf{x} \in \mathbb{Z}^n}$$ 同理可得，我们可以用线性代数中学到的基变更（Change of basis）给这个Lattice找到一组新的基$ \mathbf{C} $。…

浅谈零知识证明之四：zkSNARK证明体系的实现（下） 前段时间略忙，主要时间在研究全同态算法FHE和可信多方计算MPC方面的内容，所以迟迟没有写完zkSNARK具体实现的下篇。这次回来补上下篇！ 回顾一下上一期，我们讲到了PCP定理，并且从PCP定理出发约束到了LPCP。随后我们讲到了如何用Fiat-Shamir把交互式的协议压缩成非交互式协议。最后我们学习了R1CS矩阵程序，以及如何从R1CS矩阵得到对应的多项式表达式。 掌握R1CS之后，其实距离我们的结果zkSNARK已经不远了。今天这一期我们着重的了解一下，从R1CS电路到zkSNARK需要经过的三大步： 从R1CS电路出发，建立我们的线性PCP（LPCP）交互式证明系统。 把LPCP交互系统转换成需要可信初始化的非交互式简短证明（SNARK w/ Trusted Setup）。 加入零知识（zk）。 话不多说，我们开始吧。 从R1CS到LPCP 上一期结束的时候，我们大致的介绍过如何把区间证明的电路转换成R1CS矩阵程序，最后再转换成多项式。想必大家都大致了解了如何把R1CS的三个矩阵转换成多项式的过程——通过范德蒙矩阵$ V $来把$ A, B, C $矩阵转换成三个多项式$ P(x), Q(x), R(x) $。 R1CS转换为多项式 上一期我们看到的$ A, B, C $变成$ P(x), Q(x), R(x) $只是一个方便大家理解而描述的例子，这一期我们先来系统性的概括总结一下从R1CS是如何转换到多项式的。 首先，我们使用$ m, n $来定义R1CS的三个矩阵$ A, B, C \in \mathbb{F}^{m \times (n+1)} $的维度。对于R1CS程序对应的公有和私密输入，我们使用$ \vec{z} = \begin{bmatrix}1\x\w\end{bmatrix} \in \mathbb{F}^{n + 1} $来表达。这里$ m $代表的就是R1CS电路中有多少条约束（constraint），而$ n $代表了一共有多少个输入变量（$ x + w $）。因为我们还需要用到常数1，所以矩阵的维度是$ m \times (n + 1) $。 随后，我们将$ A $还原为多项式$ f(x) $。就像前一篇所述，我们找到多项式$ f(x) $的多个取值点：$ f(i) = (A \cdot \vec{z})_i \text{ for } i = 1, …, m $。我们一共会得到$ m $个取值点，然后就可以使用范德蒙反矩阵把这些取值点还原成一个$ m-1 $阶的多项式。 对于$ B $，我们也进行同样的操作，还原$ g(x) $。 最后对于$ C $，我们首先设定$ h(i) = (C \cdot \vec{z})_i \text{ for } i = 1, …, m $，然后由于$ h $的阶度会是$ f, g $的阶度之和（即$ 2m - 2 $），我们需要额外定义$ m - 1 $个点的取值（这样我们就有$ 2m - 1 $个取值点，可以还原$ 2m - 2 $阶的多项式）。我们额外设定$ h(i) = f(i) \cdot g(i) \text{ for } i = m+1, …, 2m-1 $，随后就可以还原出多项式$ h(x) $。 因为多项式保持了原先矩阵之间的关系，如果R1CS矩阵之间满足$ (A \cdot \vec{z}) \circ (B \cdot \vec{z}) = C \cdot \vec{z} $，通过这个方法得到的$ f, g, h $一定会满足$ f(i) \cdot g(i) = h(i) $。反过来也是一样，如果我们可以找到三个多项式并且$ h = f \cdot g $，那么代表这三个多项式所对应的R1CS矩阵程序一定也满足$ (A \cdot \vec{z}) \circ (B \cdot \vec{z}) = C \cdot \vec{z} $的关系。…

初探全同态加密之三：构建GSW全同态加密系统 上一期的文章中，我们一起了解了格密码学到底是什么，随后我们学习了LWE问题的构造。最后，我们把所学的内容组合起来，构成了格密码学中最经典的Regev加密算法。 希望看到这里，大家已经对上期讲到的内容已经有一个深刻的认知了。这一期，我们就可以真正开始实战最后的boss——开始构造全同态加密系统。 上期回顾 在开始之前，为了便于大家能够更好理解这期会描述的FHE系统，我们在此快速的复习一下之前两期文章讲到的比较关键的知识点。 LWE问题 上期文章中较为重点的内容就是LWE问题了。可以说正确的理解了LWE，格密码学和FHE问题就已经搞定了一大半了。 总结起来说，一个LWE的问题实例会随机生成一个比较大的矩阵$ A $，和一个不公开的私密向量$ s $。**搜索LWE问题（SLWE）**就是给定一个$ A $，以及带有误差的乘积$ (As + e) $，尝试还原出未知的向量$ s $。决策LWE问题（DLWE）就是分辨看到的一组矩阵与向量究竟是一个LWE实例$ (A, As + e) $，还是随机生成的矩阵$ (A, v \in \mathbb{Z}_q) $。一个合理构造的SLWE与DLWE问题在格密码学中都被定义为困难的问题。 为了更好的理解DLWE问题为什么是困难的，我们不妨看一下这张图。 上面的图中，我们可以看到$ As + e $是通过矩阵相乘得到的。因为$ As + e $与$ A $都有$ m $行，所以我们可以把他们拼在一起，当作一个矩阵$ (A, As + e) $来看待。因为SLWE是困难的，所以我们无法从$ As + e $中有效的还原$ s $，这也就是说$ As + e $对于我们观察者来说，和随机的向量$ v $没有区别。这样一来，$ (A, As + e) $这么一个矩阵对于我们来说，和一个在$ \mathbb{Z}_q $中随机生成的$ m \times (n+1) $的矩阵也没有任何区别。…

In my previous post, I went over how Lattice-based crypto works, as well as what Learning With Error (LWE) Problem is. In the end, we looked at how Regev Encryption works by putting the LWE problem together with an encryption scheme. Hopefully, everyone should have a pretty solid understanding about these fundamental building blocks. Now we are finally ready to battle the archnemesis - building the actual FHE scheme. Recap Before we begin, let’s do a quick recap of what we have learned before.…

初探全同态加密之二：格密码学与LWE问题 上一期文章中，我们一起学习了**全同态加密（FHE）**的定义和具体的几个阶段，并且也回顾了FHE的历史。到这里，大家应该对FHE系统已经有一个比较初步的了解了。 我们在上一篇文章的结尾提到了GSW系统，也就是我们所说的第三代全同态加密系统。GSW系统的构造主要是基于格密码学中有名的LWE问题假设。为了更加方便与我们来了解GSW系统的具体构造，我们这期文章来快速地学习一下，格密码学与LWE问题究竟是什么。 格密码学（Lattice-based Crypto）是现在比较火的一个密码学分支，而且本身拥有抵抗量子计算的特性。在即将到来的NIST后量子时代加密算法标准化讨论中，基于格的加密体系就是其中的一个选择之一。不过大家不要被这些定义吓到了，其实想要理解格密码学非常简单，我们只需要一些最基本的线性代数知识。 PS：如果对线性代数内容比较生疏的话，笔者强烈建议去看3Blue1Brown大神的视频合集线性代数的本质。视频里面非常生动的描述了线性代数的基本定理。 格密码学快速入门 到底什么是格密码学？听了半天想必大家还没搞明白，其实格密码学就是基于**格（Lattice）**和格上的一些问题而定义的一套密码学体系。所以我们需要先搞明白，格到底是什么。 为了更加方便的举例子，我们这里介绍一个最简单的格系统——整数格（Integer Lattice）。 整数格（Integer Lattice）的构造 在线性代数中，我们都知道，如果要描述一个线性空间$ V $的话，我们可以找到一个代表这个空间的一组基（Basis）。反过来说，如果我们知道一个线性空间拥有两个基向量（Basis Vector）$ b_0, b_1 $，那么在这个空间里的任意一个向量都可以被分解为这两个基向量的任意线性组合。 举个例子，假如线性空间$ V $拥有两个基向量$ b_0, b_1 $，那么这个空间中的任何一个向量$ v $都可以被表示为： $$ v = c_0 \cdot b_0 = c_1 \cdot b_1$$ 这里$ c_0, c_1 $可以是任何数字。我们也可以通过改变$ c_0, c_1 $这两个数字的值来改变最后生成的向量$ v $。用这种方法可以生成的所有向量$ v $最后就会组成一个线性空间$ V $，我们称这个空间为$ b_0, b_1 $两个基向量的线性生成空间（Span）。 我们日常生活中最常见的线性生成空间，就是**XY坐标系（笛卡尔坐标系）**了。笛卡尔坐标系的基向量就是两根坐标轴对应的单位向量$ \hat{i} = \begin{bmatrix}1\0\end{bmatrix}, \hat{j} = \begin{bmatrix}0\1\end{bmatrix} $。任何在XY坐标系中的向量$ v = \begin{bmatrix}x\y\end{bmatrix} $，都可以用$ \hat{i}, \hat{j} $的线性组合来代表。 现在，如果我们再给这一个线性空间系统加上一个约束：所有的线性组合系数$ c_i $都必须是整数（Integer），那会和之前有什么不同呢？…

Fully Homomorphic Encryption Part Two: Lattice-based Crypto and the LWE Problem Last time, we went through the overview of what FHE is, the different stages towards FHE, and the brief history of it. I think at this point, we should be pretty comfortable with understanding what FHE is and its potential applications. We concluded the last post by alluding to this GSW FHE Scheme. It’s the 3rd Gen FHE Scheme based on the LWE Problem assumption which stems from Lattice-based Cryptography.…