简述
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}$$