格密码

2022-04-12 本文已影响0人雪落无留痕

好看没看格密码了，今天回顾下格密码的一些基础。

格基础知识

定义已知 $\mathbf{B} = \{b_i \in \mathbb{R}^n\}$ 是 $n$ 个线性无关的向量，则基于 $\mathbf{B}$ 的 $n$ 维格 $\mathcal{L}$ 定义为：
$\mathcal{L}(B) = \{ \sum_{i=1}^na_i\mathbf{b_i}: a_i \in \mathbb{Z} \}$
其中 $\mathbb{R}^n$ 表示为 $n$ 维实数域， $\mathbb{Z}$ 表示为整数域， $\mathbf{B}$ 称为格 $\mathcal{L}$ 的一组基，若基向量的个数和格的维度相等，则称为满秩格。

格具有以下性质：

加法子群： $0 \in \mathcal{L} \subset \mathbb{R}^n$ 且对于任意的 $\mathbf{x,y} \in \mathcal{L} \subset \mathbb{R}^n$ , 有 $-\mathbf{x}, \mathbf{x+y} \in \mathcal{L} \subset \mathbb{R}^n$ ;
离散性：对于任意 $\mathbf{x} \in \mathcal{L}$ ，且存在 $\epsilon > 0$ ，满足 $\mathcal{L} \cap \{\mathbf{y} \in \mathbb{R}^n : \|\mathbf{x}-\mathbf{y}\| < \epsilon \} = \{\mathbf{x}\}$

若有矩阵 $\mathbf{B}$ 表示格 $\mathcal{L}$ 的基，且基向量为列向量，表示为： $\mathbf{B={b_1, b_2,\cdots, b_n}}$ , 设 $\mathbf{a}=[a_1, a_2, \cdots, a_n]$ 也为列向量，则基于 $\mathbf{B}$ 的格 $\mathcal{L}$ 可以表示为：
$\mathcal{L}\mathbf{(B)= \{Ba: a\in \mathbb{Z}^n \}}$
定义已知 $\mathbf{B}=\{\mathbf{b}_i\in \mathbb{R}^n: 1\leq i \leq n \}$ 是 $n$ 维格 $\mathcal{L}$ 的一组基，则格 $\mathcal{L}$ 关于 $\mathbf{B}$ 的元域（Fundamental Domain ） $\mathcal{F}$ 表示为：
$\mathcal{F}(\mathbf{B})= \{\sum_{i=1}^na_i\mathbf{b}_i: a_i\in [0,1) \}$
命题已知 $\mathbf{B}=\{ \mathbf{b}_i\in \mathbb{R}^n: 1\leq i \leq n \}$ 是 $n$ 维格的 $\mathcal{L}$ 的一组基，则有 Hadamard不等式：
$det \mathcal{L} \leq \prod_{i=1}^n\|\mathbf{b}_i\|$
定义Hadamard 比为：
$\mathcal{H}(\mathbf{B})=(\frac{det\mathcal{L}}{\prod_{i=1}^n \| \mathbf{b}_i\|})^{1/n}$
对于格 $\mathcal{L}$ 的什么任意一组基，都有 $0\lt \mathcal{H}(\mathbf{B})\leq 1$ ，该比值反映基的两两正交性，若比值接近于1，则表示基越近于两两正交。通常，将Hadamard 比接近于1 的基称为好基，接近于0的基称为坏基。

格问题

定义格 $\mathcal{L} \subset \mathbb{R}^n$ 的最短向量距离是指格中最短的非零向量。
$\lambda_1(\mathcal{L}) = min_{v\in L \setminus \{0\}}\|\mathbf{v} \|$
大部分格的问题都汲及到格中两个向量或者格中的向量与非格中向量的距离问题，格中的距离一般指欧氏距离。

最短向量问题（SVP） 已知 $n$ 维格 $\mathcal{L}$ ，找到格 $\mathcal{L}$ 中最短非零向量，即找到向量 $\mathbf{v} \in \mathcal{L}$ ，满足：
$\|\mathbf{v} \|= \lambda_1(\mathcal{L})$
近似最短向量问题（ $SVP_{\gamma}$ ） 已知 $n$ 维格 $\mathcal{L}$ 和 $\gamma$ ，找到 $\mathcal{L}$ 中的非零向量 $\mathbf{v} \in \mathcal{L}$ ，满足：
$\|\mathbf{v} \| \leq \gamma(n) \lambda_1(\mathcal{L})$
其中 $\gamma$ 是格维度 $n$ 的函数。

最近向量问题（ $CVP$ ） 已知 $n$ 维格 $\mathcal{L}$ 和一个非 $\mathcal{L}$ 中的向量 $\mathbf{w} \in \mathbb{R}^n \setminus \mathcal{L}$ ，找到 $\mathcal{L}$ 中向量 $\mathbf{v}$ ，使得 $\|\mathbf{v} -\mathbf{w} \|$ 最小。

近似最近向量问题（ $CVP_{\gamma}$ ） 已知 $n$ 维格 $\mathcal{L}$ 和一个非 $\mathcal{L}$ 中的向量 $\mathbf{w} \in \mathbb{R}^n \setminus \mathcal{L}$ ，找到 $\mathcal{L}$ 中向量 $\mathbf{v}$ ，满中：
$\|\mathbf{v} - \mathbf{w} \| \leq \gamma(n)min_{u \in L} \|\mathbf{u} -\mathbf{w} \|$
其中 $\gamma$ 是格维度 $n$ 的函数。

最小整数解问题（SIS） 给定矩阵 $A \in \mathbb{Z}^{n \times m}_q$ , 找到向量 $x$ ，满足 $Ax=0\ mod\ q$ 且 $0 < \| x \| \leq \beta$ 。

其中 $\mathbb{Z}^{n \times m}_q$ 表示 $n$ 行 $m$ 列的矩阵，且元素范围为： $|-\frac{q-1}{2}, \frac{q-1}{2}|$ , $q$ 为质数。

SVP 和 CVP 特定条件下都是难于计算的，CVP 问题是NP-hard 问题，常规 SVP 问题在随机约减情况下也是NP-hard问题。基于不同的难题，就有不同的格密码体制。

最短向量问题

命题已知 $n$ 维格 $\mathcal{L}\subset \mathbb{R}^n$ ，则 $\lambda_1(\mathcal{L}) \leq \sqrt{n}\ det\mathcal{L}^{\frac{1}{n}}$ .

命题已知 $n$ 维格 $\mathcal{L}\subset \mathbb{R}^n$ ，则 $\lambda_1(\mathcal{L}) \leq \sqrt{\frac{2n}{\pi e}}\ det\mathcal{L}^{\frac{1}{n}}$ .

Babai 最近向量算法

已知 $n$ 维格 $\mathcal{L}\subset \mathbb{R}^n$ ，有一组基 $\mathbf{B} = \{\mathbf{b_i}\in \mathbb{R}^n: 1\leq i \leq n \}$ ， $\mathbf{w} \in \mathbb{R}^n \setminus \mathcal{L}$ 是非格向量，如果 $\mathbf{B}$ 中的向量两两正交或接近两两正交，则可以采用Babai算法求解CVP。

$\begin{aligned} & 输入：一组好基 \mathbf{B} = \{\mathbf{b_i}\in \mathbb{R}^n: 1\leq i \leq n \}, 非格向量\mathbf{w} \in \mathbb{R}^n \\ & 输出：向量 \mathbf{v}，使得 \|\mathbf{v} -\mathbf{w} \| 最小\\ &\ \ \ \ \ \ \ \ \ 1.\ 用基向量表示\mathbf{w}, \mathbf{w}\leftarrow \sum_{i=1}^n w_i\mathbf{b_i} \\ &\ \ \ \ \ \ \ \ \ 2.\ \mathbf{v}\leftarrow \sum_{i=1}^n \lceil w_i\rfloor\mathbf{b_i}, \lceil w_i\rfloor 表示四舍五入 \\ &\ \ \ \ \ \ \ \ \ 3.\ 返回\mathbf{v} \end{aligned}$

GGH 数字签名

Goldreich, Golfwasser和Halevi 于1997年提出一种基于CVP问题的数字签名算法，简称GGH 数字签名。GGH密码中，私钥是 $n$ 维格的 $\mathcal{L} \subset \mathbb{R}^n$ 的一个好基，公钥是同格的坏基，密钥生成算法如下：
$\begin{aligned} & 输入：维度 n \\ & 输出；私钥 sk, 公钥 pk \\ &\ \ \ \ \ \ \ \ 1.\ 生成一个好基\mathbf{V}, \mathbf{V}\leftarrow \mathbb{Z}^{n\times n}, \mathcal{H}(\mathbf{V})\approx 1; \\ & \ \ \ \ \ \ \ \ 2.\ 生成一个坏基\mathbf{W}, \mathcal{H}(\mathbf{W})\ll 1; \\ & \ \ \ \ \ \ \ \ 3.\ 私钥 sk \leftarrow \mathbf{V}; \\ & \ \ \ \ \ \ \ \ 4.\ 公钥 pk \leftarrow \mathbf{W}; \\ & \ \ \ \ \ \ \ \ 5.\ 返加（sk, pk）; \end{aligned}$
数字签名，选择一个非格向量 $m \in \mathbb{R}^n$ 作为签名明文，用好的基求解向量 $m$ 的CVP 问题，返回的向量即为签名，如下所示：
$\begin{aligned} & 输入：私钥 sk, 明文 m \\ & 输出；签名 s \\ &\ \ \ \ \ \ \ \ 1.\ 用Babai 算法求解 \mathbf{s}\leftarrow solveCVP(\mathbf{V,m}); \\ & \ \ \ \ \ \ \ \ 2.\ 返回 \mathbf{s} \\ \end{aligned}$
验证签名的过程就是判断签名明文 $\mathbf{m}$ 是否与签名 $\mathbf{s}$ 足够近，可以验证明文 $\mathbf{m}$ 与签名 $\mathbf{s}$ 的距离是否小于 $\sqrt{n\sigma}(\mathcal{L})$ 进行判断，其中 $\sigma(\mathcal{L})=\sqrt{\frac{n}{2\pi e}}det {\mathcal{L}}^{\frac{1}{n}}$ ，用坏的基计算格的行列式，算法如下：
$\begin{aligned} & 输入：签名 s, 明文 m \\ & 输出；接收或拒绝 \\ &\ \ \ \ \ \ \ \ 1.\ 如果\|\mathbf{s-m} \|\leq \sqrt{n}\sigma(\mathcal{L})，则接受; \\ & \ \ \ \ \ \ \ \ 2.\ 否则，拒绝\\ \end{aligned}$
2012年，Lyubashevshy提出一种基于SIS 的数字签名方案，本文不在详细介绍。

参考

https://hal.inria.fr/hal-00864308

格密码

格基础知识

格问题

最短向量问题

最近向量问题

Babai 最近向量算法

GGH 数字签名

参考

猜你喜欢

热点阅读