0%

SIS 问题

发表于 更新于 分类于

和基于数论的公钥密码学依靠诸如 RSA、DDH 和 CDH 等困难问题假设类似，基于格的密码学同样有着这样的困难问题假设，分别为 SIS（Short Integer Solution）问题和 LWE（Learning With Errors）问题。这里我们先来详细介绍 SIS 问题。

SIS 问题的定义

SIS 问题最初由 Ajtai [Ajt96] 提出，它的定义如下：

Short Integer solution $(\mbox{SIS}_{n, q, \beta, m})$

Given $m$ uniformaly random vectors $\mathbf{a_i} \in \mathbb{Z}_q^n$, forming the columns of a matrix $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$, find a nonzero integer vector $\mathbf{z} \in \mathbb{Z}^m$ of norm $||\mathbf{z}|| \le \beta$ such that

— by [Pei16] in p.18

SIS 问题的讨论

在看完定义后我们会发现，SIS 问题在形式上类似于一个线性方程求解问题，即“Integer Solution”，但真正让 SIS问题有密码学价值的是对解的约束条件，即“short”，也就是求出的线性方程的解的模必须要足够小（也就是定义当中说的 $||\mathbf{z}|| \le \beta$）。否则的话，如果不对解加以约束，则只需要通过高斯消元法（Gaussian Elimination）就可以完全解决这个问题。明确了这一点后，很自然地下一个问题就是限制条件 $\beta$ 到底应该怎么选？

关于参数 β 的选择

首先很显然，$\beta$ 不能太大，比如说若 $\beta \ge q$，那么很显然就存在一个平凡解为 $\mathbf{z} = (q, 0, \cdots, 0) \in \mathbb{Z}^m$，这个问题同样就没有意义了；其次，$\beta$ 也不能太小，因为太小很有可能就导致整个问题根本没有符合条件的解。一个保证有解的参数选择为：$m \ge n \cdot \log q$ 而 $\beta \ge \sqrt{m}$ （事实上都是略大于而不是远远大于）它的推导过程如下：

考虑映射 $f_{\mathbf{A}}: \{0, 1\}^m \to \mathbb{Z}_q^n$，不难发现这个映射的定义域（domain）大小为 $2^m$，值域（range）大小为 $q^n$。若按照上述参数选择，则可以得到 $2^m \ge q^n$。按照鸽巢原理（Pigeonhole Principle），映射 $f_{\mathbf{A}}$ 就必然存在碰撞（collision），即存在 $\mathbf{x, x’} \in \{0, 1\}^m$ 满足 $\mathbf{Ax = Ax’}$。两式相减有 $\mathbf{A(x-x’) = 0}$，于是就可以构造出一个 SIS 解 $\mathbf{z = x-x’} \in \{0, \pm 1\}^m$，它满足约束 $||\mathbf{z}|| \le \beta$。这就证明了 SIS 解的存在性。

SIS 问题的 lattice 表示

说到这里我们都还是在 $\mathbb{Z}^m$ 域中讨论一个线性方程求解的问题，而要使用这个 SIS 问题去构造基于格的密码学，我们还需要一个小小的跳跃，就是将线性方程和某个格（lattice）对应起来。这其实很好办到，因为不论是线性方程的解还是格点（lattice point）都是 $\mathbb{Z}^m$ 域中的一个元素（即一个 $m$ 维向量），因此我们可以定义如下形式的格表示与之对应的 SIS 问题：

为了方便理解，下面给出 2 维的示意图来阐述 SIS 问题与 lattice 的对应关系，从图中可以看出，SIS 问题就是找距离原点某一小范围内的格点。需要注意的是，$\mathcal{L}^{\perp}(\mathbf{A})$ 其实是在空间中无限延伸的，下图只是画了它的延伸单元，即 $q \times q$ 范围内的一小部分。

sis

SIS 问题的变种

定义中给出的其实是齐次（homogeneous）版本的 SIS 问题，即等式右边是 $\mathbf{0}$。而如果将等式右边改为一个 $n$ 维常向量 $\mathbf{u}$，这个变种问题就称为非齐次（inhomogeneous）版本的 SIS 问题。不难发现非齐次的 SIS 问题对应的 lattice 表示为：

其中 $\mathbf{c}$ 为任何一个（不一定要是“short”）非齐次 SIS 的解，即 $\mathbf{Ac=u}$。因此 $\mathcal{L}^{\perp}_{\mathbf{u}} (\mathbf{A})$ 其实可以认为是 $\mathcal{L}^{\perp} (\mathbf{A})$ 的一个偏移（offset）。

参考资料