摘要 本文介绍了基于格密码学困难问题 SIS 与 LWE 的单向哈希函数构造方法。首先回顾了 Ajtai 在 1996 年提出的基于 SIS 的单向函数构造，说明其安全性来源于 SIS 问题的平均情况与最坏情况困难性的等价性，并指出该函数具有满射性与抗碰撞性。随后，进一步探讨了基于 LWE 的单向哈希函数。LWE 问题可视为随机格上的 BDD 问题，因此具有强大的平均情况困难性保障。基于 LWE 的单向哈希函数不仅构造更加简洁，而且是单射函数，每个实例有唯一解，与 SIS 构造存在本质差异。
1. SIS 问题
Ajtai 在 1996 年提出了基于 $q$ 阶随机格构造单向函数的方法。基于格密码的困难问题 SIS（最短整数解，short integer solution） 构造的，并且给出了安全论证，原理概述如下：
随机生成一个矩阵$A \in \mathbb{Z}_q^{m \times n}$这是公开部分。
SIS 问题： 寻找一个短向量$x \in \mathbb{Z}^n$，使得$Ax = 0 \mod q$。
这是 最短整数解问题（SIS）。可以看作是 $q$ 阶格 $\Lambda_q(A)$ 上的最短向量问题，是格密码学中公认的困难问题。为了计算简单，一般选取 $x$ 为二进制向量。
1.1 单向哈希函数的构造
Ajtai 根据 SIS 的困难性构造出一个单向哈希函数 $f_A$：令 $m > n \log q$，定义$f_A : {0,1}^n \to \mathbb{Z}_q^m$，具体为$f_A(x) = A x \mod q$。
1.2 单向性
从线性代数角度看，给一个矩阵 $A$ 和 $b = f_A(x)$，求 $x$ 在一般情况下很容易。但是，要求 $x$ 是一个短向量却是困难的。
对 $Ax = b$，可以表示为：
- 一个特解 $t$，满足 $At = b \pmod q$；
- 加上一个齐次解 $y$，满足 $Ay = 0 \pmod q$。
因此，解 $x = t + y$ 实际上对应于在格 $\Lambda_q(A)$ 上找到一个接近点 $t$ 的短向量问题。这等价于 近似最短向量问题（ADD 问题） 和 界定距离解问题（BDD 问题）。而 ADD 问题又可进一步归约到 SIVP 问题，其困难性显而易见。
1.3 满射与抗碰撞性
在选择参数时，一般会让 $q$ 较小，使得函数 $f_A$ 是一个 满射函数。这意味着会有多个不同的短向量 $x, y$ 满足$f_A(x) = f_A(y)$。即一定存在 碰撞（collision）。
但 Ajtai 证明了该函数具有抗碰撞性（collision resistance）。即使存在碰撞，给定一个 $x$，也无法高效找到另一个对应的 $y$。
1.4 意义与改进
注意，ADD 问题和 BDD 问题是平均情况下的格问题。因此，Ajtai 的工作将格问题的平均情况困难性与最坏情况困难性联系在了一起。Ajtai 的工作随后被改进与简化 [1, 2]，最好的已知结果来源于论文 [3]，并在文章 [4] 中得到提炼。
2. 基于 LWE 的单向哈希函数
可见根据 SIS 问题 可以构建格上的单向哈希函数，甚至构造陷门单向函数。同理，能够基于LWE 问题也够构建这些密码函数。
2.1 LWE 判断问题与单向性
-
LWE搜索困难问题： 已知矩阵$\mathbf{A}\in \mathbb{Z}_q^{mn}$和向量$\mathbf{b}\in \mathbb{Z}_q^{m}$，求向量$\mathbf{s}\in\mathbb{Z}_q^{n}$是困难的。其中，$\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}\mod q$， $\mathbf{e}\in \mathbb{Z}_N^{m}$是噪声（欧几里得范数很小）。
-
LWE判决困难问题： 已知矩阵$\mathbf{A}\in \mathbb{Z}_q^{mn}$和向量$\mathbf{b}\in \mathbb{Z}_q^{m}$，判断是LWE实例，还是随机数实例。
2.2 LWE 问题与格问题的关系
在上述 LWE 问题的定义中，对于 $m$ 个从 $A s + e$ 取出的独立实例，可以表示为：
$$
A \in \mathbb{Z}_q^{m \times n}, \quad b = A s + e
$$
其中，$As$ 可以看作是格 $\Lambda_q(A^T)$ 上的一个点 （换言之，根据上一节的SIS问题，$f=As \mod q$是一个抗碰撞哈希函数，将数据映射到格点。），因此，加入噪声 $e$ 后，其结果就是该格点附近的一个向量。 若要求解原始格点，就相当于求解 最近向量问题（CVP）。
2.3 与 BDD 问题的联系
由于要求噪声 $e$ 的值较小，这与 BDD（Bounded Distance Decoding）问题的条件一致。因此，LWE 问题可以看作是随机格 $\Lambda_q(A^T)$ 上的 BDD 问题。
2.4 LWE 搜索问题与单向性
根据 LWE 搜索问题的困难性，即给出 LWE 实例 $(A, b)$，要求解 $s$ 是困难的，就可以定义单向函数的单向性，从而构建单向哈希函数。定义如下函数：
$$
f_u(s, e) = A s + e \pmod q, \quad s \in \mathbb{Z}_q^n, \ e \in \mathbb{Z}_q^m
$$
特点
- 相比于在 SIS 上构建单向哈希函数，在 LWE 上构建单向哈希函数更加简单。
- 上述基于 LWE 的单向哈希函数是单射函数，因此每一个 LWE 问题都有唯一解 。
- 这与 SIS 上的单向哈希函数不同，SIS 上的函数是满射，存在碰撞。
结论
SIS 与 LWE 两类格问题为构造安全的单向哈希函数提供了坚实的理论基础。其中，SIS 构造保证了抗碰撞性并开启了格密码学的发展，而 LWE 构造则在形式上更为简洁，并且具备良好的平均情况安全性。这些研究成果奠定了现代格密码的基石，也为后续基于格的加密、签名和功能性密码方案的发展提供了重要支撑。
参考文献
- Goldwasser S., Kalai Y., Popa R. A., et al. Reusable garbled circuits and succinct functional encryption [C]. Proceedings of the 45th Annual ACM Symposium on Theory of Computing. Palo Alto, California, USA: ACM, 2013: 555–564.
- Van Dijk M., Gentry C., Halevi S., et al. Fully homomorphic encryption over the integers [C] // Gilbert H. Advances in Cryptology – EUROCRYPT 2010. Springer Berlin/Heidelberg, 2010: 24–43.
- Micciancio D., Regev O. Worst-case to average-case reductions based on Gaussian measures [J]. SIAM Journal on Computing, 2007, 37(1): 267–302.
- Gentry C., Peikert C., Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions [C]. Proceedings of the 40th Annual ACM Symposium on Theory of Computing. ACM, 2008.
