格（Lattice）学习笔记之八：SIS OWF的应用

Original 东泽安比技术社区 2020-08-20 12:30

本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。

到这儿，和SIS有关的内容就了解的差不多了。最后一篇来讲讲SIS OWF的实际应用。

SIS的压缩属性与CRHF

首先我们看SIS OWF的结构：

因为Ajtai给出的安全定义——即，这也就是说我们原来有 bits的信息量，我们等于是把它压缩到了个模中的数字，即个bits的信息量。这也正好符合了SIS OWF满射（surjective）的特性，输入空间比输出空间大得多。

基于这一压缩的特性，我们很自然的就可以用SIS OWF来做一个Collision Resistant Hash Function。具体的CR和单向性我们之前也讨论过了。为了巩固知识，我们再来推一边。

首先，SIS OWF的单向性不用多说，因为SIS是一个公认的格中难题，如果我们可以逆向计算SIS的话，那也就代表我们可以解决格中的SIVP问题。

接着，我们需要证明如果SIS OWF是单向的，那么它也是Collision Resistant的。这个证明也不难，我们反过来推，如果我们可以找到SIS OWF的碰撞，那么我们就可以破解它的单向性。

假如给定一个，我们想要找到一个使得：

那么，我们首先可以在矩阵的任意一个column中（假设是第列，即）加上的值，构成。注意因为是一个随机的矩阵，所以就算某一列加上了，这个矩阵仍然还是随机的。

这个时候，我们可以尝试找到的碰撞，即一组：

得到了碰撞之后，我们检查的第位是否不同。如果，那么我们就可以得到：

这里的值也就是前面SIS OWF的解了。具体的原理也很简单，因为如果，那么代表并不会用到我们修改过的这一列，这也就代表。同理，因为，所以。我们把两边相减，就能得到我们原来的了。

SIS的输出随机分布与承诺

SIS OWF不仅是单向且CR的，而且它的输出也是呈随机分布的。这一点我们可以用Leftover Hash Lemma来进行归纳。

LHL指出，如果一个函数具有Pairwise Independence，并且输出空间小于输入空间（压缩），那么这个函数的输出就为随机分布。

首先来看Pairwise Independence这一点，它的定义就是，如果任意固定两个输入，然后我们随机选择一个SIS问题，如果这两个SIS OWF的输出分布是独立的，那么这就代表这个函数是成对独立的（Pairwise Independent）。

当满足随机分布的条件之后，那么我们就可以把的输出看做一个随机分布的向量：

基于这一特性，我们就可以构建一个承诺（Commitment）系统。一方可以生成一段信息的承诺，然后把这个承诺发送给另一方。承诺的本身并不能暴露的值，即需要满足hiding的属性。稍后，承诺方可以公布一段字串来“打开”这个承诺，随后另一方就可以验证这个承诺的确是从信息构造而来的。一个承诺打开的方法应该只能有一种，即需要满足binding的属性。

我们基于SIS OWF来尝试构建一个承诺系统：

首先，我们选择两个随机的SIS问题矩阵。
假如我们要承诺信息，那我们随机选择一个向量，然后我们输出承诺。
注意到这里因为都是随机生成的，所以基于SIS OWF的随机分布特性，这等于是在我们原本的上叠加了一层随机的One-Time Pad，所以整体承诺也是随机分布的。
同样，这个承诺也是binding的，因为如果我们能够找到一对不同的并且可以得到同样的承诺的话，那就等于是我们找到了的一对碰撞，这我们已经证明了是不可能的。