Lattices and Cryptography（格理论与密码学）

2024-03-25 16:33:22

本文是阅读 Introduction of Mathematical Cryptography Second Edition 一书中关于格密码一章的Review，只讲述简单的总结，具体内容请翻阅该书的第七章（下文中大部分图片均来自此书）

同余密码体系与背包密码

同余(Congruence)密码 流程如下，可以看做一个低维的格密码，破解该种密码可以相当于找一个向量，这个向量就是私钥

将上面这个问题用向量的形式写出来，就是要找一个 $a_1,a_2\in \mathbb{Z}$ a1,a2∈Z来找到一个小的向量，如下面的表达式所示
$L=\{a_1v_1+a_2v_2:a_1,a_2\in\mathbb{Z}\}$ L={a1v1+a2v2:a1,a2∈Z}
使用格理论可以解出。
背包密码 (Knapsack Cryptosystem)关注于背包问题，一个简单的例子是Subset-sum problem，在这一章里作者举出了Merkle-Hellman subset-sum cryptosystem作为例子，如下所示：

要破解这个密码系统，我们要根据密文S获得明文 $\boldsymbol{x}$ x，就是说找到一个 $\boldsymbol{x}=\left(x_{1}, \ldots, x_{n}\right)$ x=(x1,…,xn) ，使得 $S=x_1m_1+x_2m_2+...+x_nm_n$ S=x1m1+x2m2+...+xnmn，将问题转换为下面的向量问题：
$\begin{array}{c} {\boldsymbol{v}_{1}=\left(2,0,0, \ldots, 0, m_{1}\right)} \\ {\boldsymbol{v}_{2}=\left(0,2,0, \ldots, 0, m_{2}\right)} \\ {\vdots} \\ {\boldsymbol{v}_{n}=\left(0,0,0, \ldots, 2, m_{n}\right)} \\ {\boldsymbol{v}_{n+1}=(1,1,1, \ldots, 1, S)} \end{array}$ v1=(2,0,0,…,0,m1)v2=(0,2,0,…,0,m2)⋮vn=(0,0,0,…,2,mn)vn+1=(1,1,1,…,1,S)
$L=\left\{a_{1} \boldsymbol{v}_{1}+a_{2} \boldsymbol{v}_{2}+\cdots+a_{n} \boldsymbol{v}_{n}+a_{n+1} \boldsymbol{v}_{n+1}: a_{1}, a_{2}, \ldots, a_{n+1} \in \mathbb{Z}\right\}$ L={a1v1+a2v2+⋯+anvn+an+1vn+1:a1,a2,…,an+1∈Z}
当 $\boldsymbol{x}=\left(x_{1}, \ldots, x_{n}\right)$ x=(x1,…,xn) 是明文，我们可以得到L变为 $\boldsymbol{t}$ t
$\boldsymbol{t}=\sum_{i=1}^{n} x_{i} \boldsymbol{v}_{i}-\boldsymbol{v}_{n+1}=\left(2 x_{1}-1,2 x_{2}-1, \ldots, 2 x_{n}-1,0\right)$ t=i=1∑nxivi−vn+1=(2x1−1,2x2−1,…,2xn−1,0)
根据比对L中所有可能的结果，我们可以知道 $\boldsymbol{t}$ t是L中所有可能结果中长度最小的向量，这样的话，也可以使用格理论来解出明文。

背包问题是一个难解的 $\mathcal{NP}-complete$ NP−complete 问题，一般而言不适合用来做密码系统，因为它没有trapdoor（可以理解为秘钥），但是书中的例子选用了superincreasing的公钥，使得拥有私钥的人可以很快地得出明文

向量空间

略

格理论

Lattice的定义如下

从第一个Definition到第二个Definition的证明见MIT-lattice notes

涉及到Lattice的一个重要概念是fundamental domain—— $\mathcal{F}$ F，如下图所示:

$\mathcal{F}$ F的Volume（体积？）由下面的定理给出：

当基向量相互正交， $Det(\mathcal{L})=Vol(\mathcal{F}$ Det(L)=Vol(F)获得最大值

SVP and CVP

SVP：Shortest Vector Problem
CVP：Cloest Vector Problem，给定一个不在 $\mathcal{L}$ L 中的向量 $\omega$ ω，我们需要在 $\mathcal{L}$ L中找到一个与 $\omega$ ω最近的向量
ApprSVP：

寻找SVP和CVP是格理论中最基本的问题，一般而言CVP比SVP更难，例如n维的CVP可以转换为n+1维的SVP问题

Hermite’s Theorem and Minkowski’s Theorem

Hermite定理是关于在 $\mathcal{L}$ L中的最短非零向量长度的upper bound

对于这一定理有更精确的说明如下：

$\gamma_n$ γn是赫米特常数
赫米特定理的证明依赖于闵可夫斯基定理：

这个定理描述了 $\mathbb{R}^n$ Rn的一个有界对称凸（甚至于闭）子集S若满足上述的体积与det(L)相关的不等式，那么S包含就会包含L中的向量。
举个具体的例子，在闵可夫斯基定理的百度百科，其中的L具体化为了二维坐标平面，那么坐标平面的n=2，det(L)=1，因此只要S的面积大于等于4，那么S就会至少包含一个横纵坐标都是整数的坐标，也就包含了L中的向量。

The Gaussian Heuristic

The Gaussian Heuristic（高斯启发式？）是对赫米特常数的进一步缩小（从supercube变成supersphere）

Babai’s Algorithm

这个算法是解决CVP问题的一个算法，下文中求 $a_i$ ai的方法其实就是四舍五入。

该算法对于一个“好”的基而言比较准确，对于“坏”的基而言就不是很准了，如下图所示，给定一个Target Point，利用上面的算法得到的顶点是Closest Vertex，然而直观来看最近的点应该是下图中的Closest Lattice Point，因此，当你所拥有的基是“坏”的，不容易解出CVP问题。

GGH密码

因为公钥是“坏”基，因此对于攻击者而言，使用Babai算法解出 m 可能不太现实。

NTUR密码

NTUR密码的流程如下所示：

NTUR的破解

构建这么一个矩阵：
$L_{\boldsymbol{h}}^{\mathrm{NTRU}}=\left(\begin{array}{cccc|cccc} {1} & {0} & {\cdots} & {0} & {h_{0}} & {h_{1}} & {\cdots} & {h_{N-1}} \\ {0} & {1} & {\cdots} & {0} & {h_{N-1}} & {h_{0}} & {\cdots} & {h_{N-2}} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {0} & {0} & {\cdots} & {1} & {h_{1}} & {h_{2}} & {\cdots} & {h_{0}} \\ \hline 0 & {0} & {\cdots} & {0} & {q} & {0} & {\cdots} & {0} \\ {0} & {0} & {\cdots} & {0} & {q} & {q} & {\cdots} & {0} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {0} & {0} & {\cdots} & {0} & {0} & {0} & {\cdots} & {q} \end{array}\right)$ LhNTRU=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛10⋮000⋮001⋮000⋮0⋯⋯⋱⋯⋯⋯⋱⋯00⋮100⋮0h0hN−1⋮h1qq⋮0h1h0⋮h20q⋮0⋯⋯⋱⋯⋯⋯⋱⋯hN−1hN−2⋮h000⋮q⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞
可以证明这个Lattice包含了 $(\boldsymbol{f}, \boldsymbol{g})$ (f,g)
一个定理: Let $(N, p, q, d)$ (N,p,q,d) be $NTRU$ NTRU Encrypt parameters, where for simplicity we will assume that
$p=3 \quad \text { and } \quad d \approx N / 3 \quad \text { and } \quad q \approx 6 p d \approx 2 p N$ p=3 and d≈N/3 and q≈6pd≈2pN
Let $L_{\boldsymbol{h}}^{\mathrm{NTRU}}$ LhNTRU be an $N$ NTRU lattice associated to the private $k e y(\boldsymbol{f}, \boldsymbol{g})$ key(f,g)
(a) $\operatorname{det}\left(L_{h}^{\mathrm{NTRU}}\right)=q^{N}$ det(LhNTRU)=qN
(b) $\|(\boldsymbol{f}, \boldsymbol{g})\| \approx \sqrt{4 d} \approx \sqrt{4 N / 3} \approx 1.155 \sqrt{N}$ ∥(f,g)∥≈4d≈4N/3≈1.155N
(c) The Gaussian heuristic predicts that the shortest nonzero vector in the NTRU lattice has length
$\sigma\left(L_{\boldsymbol{h}}^{\mathrm{NTRU}}\right) \approx \sqrt{N q / \pi e} \approx 0.838 N$ σ(LhNTRU)≈Nq/πe≈0.838N
Hence if $N$ N is large, then there is a high probability that the shortest nonzero vectors in $L_{\boldsymbol{h}}^{\mathrm{NTRU}}$ LhNTRUare $(\boldsymbol{f}, \boldsymbol{g})$ (f,g) and its rotations. Further,
$\frac{\|(\boldsymbol{f}, \boldsymbol{g})\|}{\sigma(L)} \approx \frac{1.38}{\sqrt{N}}$ σ(L)∥(f,g)∥≈N1.38
so the vector $(\boldsymbol{f}, \boldsymbol{g})$ (f,g) is a factor of $\mathcal{O}(1 / \sqrt{N})$ O(1/N) shorter than predicted by the Gaussian heuristic.
根据这个定理我们可以看出 $(\boldsymbol{f}, \boldsymbol{g})$ (f,g)大概率是这个格里面最短的向量，因此破解NTUR变成SVP。

LLL算法

这个算法在Size Reduction的地方有点像施密特正交化（施密特正交化脱离了整数环），下面增加了一步swap以确保满足Lovasz Condition，这样子是为了最后的基大小是从小到大排列，且最小化算法过程中的 $det L_l$ detLl( $L_l$ Ll是由 $v_1,...,v_l$ v1,...,vl生成的 $subLattice)$ subLattice)
在sage中使用LLL算法：

sage: M=Matrix(ZZ,[(1, 39245579300),(0, 122430513841)])
sage: M.LLL()
[-231231 -195698]
[-368222  217835]

使用LLL算法就可以破解比较低维的以上密码，具体例子参见课本

RayLee23333 发布了23 篇原创文章 · 获赞 1 · 访问量 1636 私信关注

码农公寓