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的概率p1必定是关于λ的可忽略函数，可以忽略不计。同时，该算法发生hash冲突的概率p2也是关于k的可忽略函数，此时的表现为找不到对应的idx值。理论分析得知，