Mythsman


乐极生悲,苦尽甘来。


Garbled Bloom Filters算法简述

简述

Garbled Bloom Filters(GBF) 算法是Bloom Filters (BF)算法的变形,并且结合了Shamir的信息分享算法,更好的解决了hash冲突的问题其形式上是将Bloom Filters算法中的BitSet数组转换成了字符串数组,数组中的每一个字符串长度为安全参数$\lambda$,可以通过调节这个参数来获得想要的安全性。该算法同Bloom Filters 一样,是一种有一定容错率的hash算法,对于存在于集合中的元素查询返回的值总是true,而对于不在集合中的元素查询的返回值大多为假,这里判断失误的概率是关于安全参数$\lambda$的可忽略函数。

初始化

1.创建一个长度为$m$的字符串数组,下标为$[0,m-1]$,数组中的每一个字符串长度均为$\lambda$,并将其置为空。
2.选择$k$个独立的均匀分布的的哈希函数$H=\{h_0 h_1 ...h_{k-1}\}$,每一个$h_i$函数映射的值域在$[0,m−1]$中均匀分布,即hash函数映射到的值总是对应字符串数组中的一个位置。
3.我们将一个$Garbled\ Bloom\ Filter$ 用$(m,n,k,H,\lambda)$表示,将需要查询的集合用$S$表示,将对于集合$S$的$GBF$用$GBF_s$表示,将其中的第i个字符串用$GBF_s[i]$表示。

插入元素

1.依次用$k$个hash函数将元素$x$映射到数组中的$k$个位置上。记录第一个hash后对应字符串值为空的位置idx,对于在这之后的hash,如果对应的字符串为空,则随机将其置为一个长度为$\lambda$的字符串,否则保持不变。
2.将上述字符串中除下标为idx的字符串之外的字符串的进行异或处理,并将结果与$x$进行异或,将得到的值赋给$GBF_S[idx]$。(Shamir 算法的体现)
3.在插入完所有元素后,将所有未被赋值的$GBF_s[i]$赋一个随机值。

查询元素

1.对于每一个待查询的元素$y$,我们用$k$个hash函数将元素$y$映射到数组中的$k$个位置上。
2.依次将这$k$个位置上的字符串进行异或,如果得到的值恰好为$y$,那么认为$y$存在于集合S中,否则不在。

删除元素

与BF算法一样不支持删除。

正确性

算法的正确性是显然的,如果$y$在集合S中,那么由于hash的过程是确定的,所以根据$Shamir$算法,将最后得到的k个字符串进行异或必然会恢复$y$。如果$y$不在集合S中,那么将那k个字符串进行异或后会恢复$y$的概率$p_1$必定是关于$\lambda$的可忽略函数,可以忽略不计。同时,该算法发生hash冲突的概率$p_2$也是关于$k$的可忽略函数,此时的表现为找不到对应的idx值。理论分析得知,$$p_1\leqslant 2^{-\lambda}$$$$p_2\leqslant1-2^{-k}$$