# 基于格的签名算法——part1
## 格密码系统发展
Ajtai在1996年提出了格上平均情况下的困难问题与最坏情况下的困难问题的等价，此结论为基于格上困难问题构造密码体制方案奠定了坚实基础。此后，基于格的公钥密码体制得到了快速的发展，具体如下：

- 1997年，Ajtai和Dwork提出首个基于格的公钥加密体制，称为Ajtai-Dwork密码系统。
- 1997年， Goldreich，Goldwasser和Halevi基于CVP问题提出了GGH密码方案。
- 1998年，Hoffstein、Pipher和Silverman提出了一个NTRU（Number Theory Research Unit）公钥密码系统。
- 2005年，Regev提出带误差学习 ( Learning With Error，LWE)问题，同时证明在量子规约下LWE问题的困难性与格上最差情况下SVP和SIVP的困难性相同，该问题在平均情况下的困难性等价于最坏情况下的GapSVP和SIVP问题的困难性。
- 2010年，Lyubashevsky，Peikert和Regev等人在LWE问题基础上进行改进，提出了环上带误差学习（Learning With Errors over Ring，RLWE）问题。
- 2010年至今，自LWE问题和RLWE问题提出后，基于格理论的密码技术发展进入了一个崭新的阶段，该类密码协议有着严格的理论安全性证明，构造的密码方案具有简洁和高安全性的特点。此后，在LWE问题和RLWE问题上出现了多种优秀的密码方案，极大促进了格密码的发展。

## 格的基本概念
### 什么是格
在线性代数中，描述一个线性空间$V$，需要找到一个代表这个空间的一组**基（Basis）**。如果一个线性空间拥有两个**基向量** $b_0,b_1$，那么在这个空间里的**任意一个向量**都可以被分解为这两个基向量的**任意线性组合**。
>eg：向量$v$都可以被表示为： $v = x_0*b_0+x_1*b_1$
其中$x_0, x_1$可以是任何数字。改变它们的生成的所有向量$v$就会组成一个线性空间$V$，而它也叫做$b_0,b_1$的线性生成空间。

最为常见的线性生成空间就是**平面直角坐标系(笛卡尔坐标系)**。

注意上面说的是一个线性空间，如果在这个线性空间加上一个约束：**所有的线性组合系数$x_i$都必须是整数（Integer）**，那么整个空间就不是一个连续的，而是一个个点组成的网格状的离散集合，即格。

其中每一个点都可以通过基向量的线性组合表达为一个独特向量，这种称为**整数格**（$n$维空间中最简单的格就是整数格），实际上还可以增加维度。

### 格的基
通过**基向量**可以表示一个格。

假设一个格拥有基向量 $b_1,...,b_n$（它们是线性无关的）。那么这个格就是它的基向量的任意线性组合的集合，可以把所有基向量组合成矩阵 $B$ 来表示。

通过格基定义一个格：$\mathcal{L}=\sum^n_{i=1} b_i * Z=\{Bx:x \in Z^n\}$

### 格的行列式(det)
>行列式就是行列式中的行或列向量所构成的平行多面体的有向面积或有向体积

在一个线性空间里面，一个空间$V$的行列式代表了这个空间中基向量$b_i$所组成的几何体的体积。在二维空间里，行列式就是两个基向量$b_1, b_2$组成的平行四边形的面积。

### 格的最短距离向量
一般用$λ_1$来定义整个格中点与点之间最短的距离，还可以定义距离第二近的点距离$λ_2$，第三近的$λ_3$，一直到第n近的$λ_n$。
所有的$\lambda_i$满足：$\lambda_1<=\lambda_2<=...\lambda_n$

## 格的难题

### SVP(Shortest Vector Problem)

**最短向量问题(SVP)**，给定一个基为$B$的格$\mathcal{L}$(B)，找到这个基构成的格点$Bx:x$，使得这个点距离0坐标点的距离最近：$Bx: x\in Z^k$ , $||Bx|| <= \lambda_1$

图中这里$\lambda_1$是这个格中点和点之间的最短距离，这个格的基向量$B=[b_1,b_2]$，我们可以找到一个点$Bx$，即$5b_1 - 2b_2$对应的这个点，正好就是这个格的最短距离向量$\lambda_1$

### CVP(Closest Vector Problem)
在**连续的二维线性生成空间**中，可以通过系数$x_i$表达出任何一个线性空间中的向量。但由于整数格是一种离散的结构，无法做到这点，比如一个向量为$v=\begin{bmatrix}2.3\\3.3\end{bmatrix}$无法在整数格中表示。

所以也就衍生出一个格的问题：既然无法表达这个向量，是否能够表达出最接近这个向量$v$的值 $v'$呢？

其实也就是说，能否在整数格中找到一组整数系数$x_0,x_1$使得$v'=x_0*b_0+x_1*b_1$ 这个向量在**这个整数格中距离目标向量v的距离最近**。

这一类在离散线性集合中逼近目标向量的问题，统称为**最近向量问题（Closest Vector Problem，CVP）**。目前已经证明，在一个足够复杂维度的空间里，CVP问题是**NP-hard**问题。

CVP问题的困难性是说，给定一组基向量 $b_0, b_1$，以及一个目标向量 $v$，我们很难有效的找到一组整数线性组合 $x_i$，使得所组成的向量 $v′$ 距离我们的目标 $v$ 最近。

严格定义是：给定一个格 $\mathcal{L}$，与一个随机点$\mathbf{t}$还有搜索距离$d$，并且假设$\mu(\mathbf{t}, \mathcal{L}) \le d$，CVP问题是让我们找到一个合理的格点${Bx} \in \mathcal{L}$并且这个点到$\mathbf{t}$的距离小于等于$d$。

## 基于格的(lattice-based)签名发展
早期的格基签名方案以 GGH 签名方案和 NTRU 签名方案为代表。但在2006年，Nguyen和Regev指出GGH签名方案及NTRU签名方案不安全。这类签名方案的私钥是较短的格基，当签名次数过多时，签名会暴露格基形成的基本区域形状，从而泄露私钥。近几年主要有以下两种方式构造基于格的签名方案:

- Gentry等人在2008年提出的GPV签名，常被称为**hash and sign**设计思路，该方案需要借助单向陷门函数进行原像采样。
- Lyubashevsky等人在2009年提出的基于**Fiat-Shamir变换**的方法，该方法不使用陷门函数，利用拒绝采样的技术避免签名泄露格基形状，该方案被认为是普通格上效率最高的签名方案。

随着应用场景的增多，还存在一些特殊性质的数字签名，如：格基**身份**数字签名，格基**盲**签名，格基**代理**签名，格基**环**签名，基于证书和无证书的格基签名等。

>在2022年7月，NIST的第三轮评估中，CRYSTALS-Dilithium（基于Fiat-Shamir）、FALCON（hash and sign），SPHINCS+上榜，其中前两个均为格密码签名方案。

### 数字签名算法流程
- 密钥生成算法(keygen)： 产生一个key pair(公私钥)
- 签名算法(sign)：(私钥，消息) $\longrightarrow$ 签名
- 验证算法(verify)：（消息，签名，公钥）$\longrightarrow$ pass?

### 格概念回顾
- **向量空间V**：任意两个向量都可以做加法运算；都可以与一个实数做标量乘法
- **格L**：任意两个向量都可以做加法运算；都可以与一个**整数**做标量乘法
- **格基**：一个格可以有多个基，这些基之间满足关系：$B_1=B_2*U$($U$为幺模矩阵) (代数角度描述格基之间的关系)
- **基本平行体**：格基围成的一个半闭半开的区域
- **格基关系**：不同的基对应的基本平行体的volume是一样的 （几何角度描述格基之间的关系）
- **行列式**：$det(L)=det(B)$，这是恒定不变的。
- **格的连续极小值**：格中最短向量的长度为格的第一连续极小，记为$\lambda_1(L)$
>1. 连续极小依赖于维度和det(L)
>2. Minkowski第一定理指出，格的最短向量长度有一个上界，即$\lambda_1(L) <= \sqrt{N} (det(L))^{(1/n)}$；格的最短向量长度有一个下界，即$\lambda_1(L) >= min ||\widetilde{b_i}||$，其中这个$\widetilde{b_i}$是施密特正交化后的基。 说明了格上点之间不是任意靠近的。
- **格上困难问题**：
- 格的代数问题是容易的，比如计算det/判断一个向量是否在一个格上
- 格的几何问题是困难的，比如计算最短向量长度等等
>尽管Minkowski给出了最短向量的下界，但是目前还没有算法可以发现该长度的短向量
典型的CVP和SVP问题都和$\lambda_1(L)$有关，SIVP问题和$\lambda_n(L)$
- **SVP,CVP,SIVP问题**
- SVP：输入$L$，找到$L$的最短向量$\lambda_1(L)$
- CVP：输入$L$和一个目标向量，找到离t最近的格点$v$
- SIVP：输入一个n维格，找到格中n个线性无关向量$b_1,b_2,...,b_n$，使得他们的长度都小于第n格连续极小$\lambda_n(L)$
>CVP和SVP可以规约到SIVP，所以解决了CVP/SVP，就可以解决SIVP
- **格基约减**：
拿一个整数格举例，CVP问题会非常简单。
因为整数格中基向量都是相互垂直的，对于给定的目标向量，我们只需要**向上或者向下取整**就可以找到最近的格点。
所以就得到一个启示：**如果能够将任意一个格转化为具有垂直基的格（格基约减）**，那么CVP问题就可以轻松解决。所以目标就是发现又短又垂直的基，而基所围成的基本平行体是大小不变的，所以只要基足够垂直，它就足够短，也就是说，我们的目标就是**发现足够垂直的基**，这个足够垂直的基就是好的格基，它和未约减的基所张成的空间是一样的
那么如何找到足够垂直的基？？？
**施密特正交化**，通过不断反复迭代，找到一组垂直的基，但是施密特正交化比较依赖向量的输入顺序，所以为了解决这个问题，1982年，产生了LLL算法，这是第一个多项式时间的格基约减算法，后来shchnorr进一步优化实现了BKZ算法。
- **陷门单向哈希函数**：单向，正向容易，逆向困难(除非有陷门)，原则上我们有了单向陷门函数，就可以构建公钥密码系统。

## GGH算法
>[Public-Key Cryptosystems from Lattice Reduction Problems](https://link.springer.com/content/pdf/10.1007/BFb0052231.pdf)
:::success
1997年，由Goldreich Goldwasser Halevi提出，它没有安全性证明。确切地说，这不是一个具体的算法，而是一个签名方案框架，可以通过这个框架来构造多种数字签名方案
:::
GGH框架最核心的基本思想是：**如果有一个好的格基，那么CVP问题就是简单的**。如果有一个好格基，就可以找到临近的格点。把好的格基作为私钥，不好的格基作为公钥。

具体的签名方案：
- 密钥生成算法：
生成同一个格的两个格基，**私钥是好的格基**，这个格基比较短，格基向量基本上是正交的，通过施密特正交化转化为正交基。**公钥是相对不好的格基**。
- 签名算法：
比如你有一个消息需要签名，你有签名算法的私钥，即一个好的格基。
首先需要进行映射，通过一个哈希函数对消息进行映射。也就是说可以把消息看成空间中的随机点$P_{m}$。

因为有私钥(好的格基)，那么就可以找到$P_{m}$的临近格点$L_{m}$，而它就是作为签名,即$\sigma = L_{m}$。

>其实我们只需要简单地把消息理解为空间中的一个点就可以了，这只是一种映射关系；然后签名算法就是把这个消息格点舍入到临近的格点

- 验证算法
- 检查这个签名是不是格点（使用公钥，高斯消元即可）
- 检查签名结果和消息的距离是不是足够近（取两个坐标的差值，求差值向量的范数即可）

>GGH签名的安全性建立在敌手无法由坏基多项式时间内恢复出好基以及敌手无法利用坏基高效求解最近向量问题(Closest Vector Problem, CVP)，但是它没有给出严格的证明。

## NTRU算法
>[NTRUSign: Digital Signatures Using the NTRU Lattice](https://www.researchgate.net/profile/Nicolas-Courtois-2/publication/221208415_About_the_XL_algorithm_over_GF2/links/0c96052b6e6726abe2000000/About-the-XL-algorithm-over-GF2.pdf#page=134)

:::success
NTRU这个格最初是2003年，由Hoffstein、Howgrave-Graham、Pipher、Silverman和Whyte在论文中提出的。它是GGH签名方案的一个非常高效的实现方法。
:::
本质上，NTRU方案是一个非常复杂、算法描述非常清晰的GGH签名方案实例。NTRU建议在GGH方案中使用一个特定的、具有非常多优秀性质的格。
这个方案的构造非常精妙，方案的运行效率高得令人惊讶，你只需要用很少的比特数来表示出这个格，但是它的构造非常复杂。用相同的格维度所构造出方案的签名长度会非常短。

- 签名长度只有1757 bits，不到2000bit
- 签名和验证比RSA快

**困难问题**：解决NTRU类型的格中的近似CVP问题(appr-CVP)

>关于NTRU lattice的构造和实现，这个以后再讨论，这里非常复杂。

>NTRUsign是不安全的，但是NTRUencrypt仍然是安全的

:::warning
GGH类算法的严重缺陷在于，攻击者可以通过多次签名的结果，得到一个大致的签名区域，这样就可以得到基本平行体的区域，从而获得好的格基，也就拿到了私钥。
Regev等人通过这个缺陷在09年攻破了GGH和NTRU签名算法。
:::

## Hash and sign
### GPV算法
>[Trapdoors for Hard Lattices and New Cryptographic Constructions](https://eprint.iacr.org/2007/432.pdf)
:::success
Gentry等人在2008年提出了GPV算法，它采用hash and sign的设计思路，是第一个可证明安全的格签名算法。主要是借助**陷门函数**进行**原像采样**
:::
GPV的核心是从任意一个n维格上进行离散高斯采样，得到一个短的原像，而不泄漏陷门。它的安全性由采样算法的高斯参数决定，而高斯参数又取决于陷门基的质量

**具有原像采样的陷门函数**
首先构造一组具有一些特殊属性的陷门函数。函数是满射的，并且是多对一的（即每个输出值都有几个原像），陷门逆函数在适合的分布下从所有原像中进行采样。

**离散高斯分布**
一般在格密码中，只考虑n维格$Λ$上的离散高斯采样
>在分布$D_{Λ,s,c}$，对于$v \in Λ$的概率为$exp(−π||v − c||^2/s^2)$，其中$c\in R^n$ 并且$s>0$; $c$是期望，$s$是标准差。

>高斯采样的范围取决于格基，而这个采样其实就是输出一个相对离c较近的格向量，它的目标其实就是和上面说的babai算法一样。

**GPV采样算法**
$(TrapGen,SampleDom,SamplePre)$满足以下条件：
- Generating a function with trapdoor：$TrapGen(1^n)$输出$(a,t)$，其中a是一个高效的计算函数$f_a: D_n \longrightarrow R_n$ ，$t$是$a$的门陷。
- Domain sampling and uniform output：通过$SampleDom(1^n)$在$D_n$上通过一些分布采样出$x$（不一定是uniform），而$f_a(x)$在$R_n$上的分布是uniform的。
- Preimage sampling with trapdoor：对于每一个$y \in R_n$ ，$SamplePre(t, y)$ 会从条件分布$x \longleftarrow SmapleDom(1^n)$中进行采样，给定$f_a(x)=y$
- Preimage min-entropy：对于每一个$y \in R_n$ ， 给定$f_a(x)=y$，$x \longleftarrow SampleDom(1^n)$的条件最小熵为$w(logn)$
- Collision-resistance without trapdoor：对于任何概率时间多项式算法$A$，$(1^n，A)$输出不同$x，x'∈ D_n$，即$f_a(x)=f_a(x')$的可能性是可以忽略的。

**签名过程**
- $SignKeyGen(1^n)$ ：$(a, t) \longleftarrow TrapGen(1^n)$ ，其中$a$是一个函数$f_a$，$t$是它的陷门。也就是说$t$可以作为签名私钥，$a$作为公钥
- $Sign(t, m)$ ：$\sigma_m \longleftarrow SamplePre(t, H(m))$，输出签名$\sigma_m$
- $Verify(a,m,\sigma)$：如果$\sigma \in D_n$ ，并且$f_a(\sigma_m) = H(m)$，验证通过

我们其实也可以把**GPV理解为一个框架**，它的思想就是单向陷门函数的原像采样实现安全的签名。

### MP12算法
>[Trapdoors for Lattices-Simpler, Tighter, Faster, Smaller](https://link.springer.com/content/pdf/10.1007/978-3-642-29011-4_41.pdf)

MP12主要是提出了一个构造陷门函数的新方法，非常高效。

前面已经介绍了，Ajtai构造了一个单项哈希函数$f_A$，它是一个满射函数，如果在该函数上引入陷门，就可以找到陷门单向哈希函数，这样就可以构造公钥密码算法，下面介绍如何构造陷门函数。

**原像可抽样函数**
$f_A$是一个单向函数，可以快速计算，但是无法从函数的输出结果有效还原输入。但是**如果知道陷门，就可以构造这个单向函数的反函数**$f_A^{-1}$，反函数需要满足一个特性：其输出空间和$f_A$的输入空间分布大致相同。（出于安全考虑，随机选择需要服从高斯分布），这种$f_A$和$f_A^{-1}$被称为**原像可抽样函数**。

> 典型的Hash-and-Sign签名，公钥是一个单向陷门函数$f(x)$，私钥是利用陷门可以高效计算的逆函数。签名是首先将消息m哈希到函数f的值域上，即$y=H(m)$，然后输出签名 $\sigma = f^{−1}(y)$。验签的时候需要检查条件$f(\sigma)=H(m)$是否成立

**构造陷门单向函数**
思路来源于均匀随机分布的特性：如果一个矩阵A是均匀随机分布的，那么在A上添加任意元素，比如加上一个矩阵，则结果依然是呈均匀随机分布。

所以就说明了一点，如果我们给A添加一些东西，使之具有特殊的结构，方便我们构造出陷门，而表面上A仍然是均匀随机分布的，无法区别与原来的矩阵A有什么不同，这样就能构造出陷门函数。

**MP12构造方法**如下：
- 构造一个具有特殊结构的矩阵G，得到相应的函数$f_G(x)$，G的结构是计算其反函数非常容易。
- 将G嵌入到均匀随机分布的矩阵A中，然后得到相应的陷门矩阵R。表面上看，叠加后的矩阵A依然是呈现均匀随机分布的，但是知道陷门后，很容易从A还原出G
- 构造$f_A^{-1}$. 这个计算可以最终规约到求$f_G^{-1}$.

>GGH提出了好的格基可以作为陷门，GPV是说我们如何通过陷门去实现安全地实现签名方案，MP是说怎么去构造一个陷门函数。

本篇文章主要从格密码签名的历史出发，介绍了格的基本概念，格的困难问题，最后介绍了格签名算法的经典框架hash and sign，后面我们会进一步介绍格签名算法的另一种框架——基于fiat shamir变换的格签名算法，同时介绍两个目前NIST推荐的格签名算法以及其他格困难问题。

## Reference
- GGH'97: [Public-Key Cryptosystems from Lattice Reduction Problems](https://link.springer.com/content/pdf/10.1007/BFb0052231.pdf)
- NTRUsign'02: [NTRUSign: Digital Signatures Using the NTRU Lattice](https://www.researchgate.net/profile/Nicolas-Courtois-2/publication/221208415_About_the_XL_algorithm_over_GF2/links/0c96052b6e6726abe2000000/About-the-XL-algorithm-over-GF2.pdf#page=134)
- GPV'08：[Trapdoors for Hard Lattices and New Cryptographic Constructions](https://eprint.iacr.org/2007/432.pdf)
- MP'12: [Trapdoors for Lattices-Simpler, Tighter, Faster, Smaller](https://link.springer.com/content/pdf/10.1007/978-3-642-29011-4_41.pdf)