Bloom-Filter加密算法

2022-10-28

近年来，随着计算机和互联网技术的发展，数据集的不断扩张使得 Bloom filter加密算法获得了新生，各种新的应用和变种不断涌现。Bloom filter加密算法是一个空间效率很高的数据结构，可以用于检索一个元素是否在一个集合中，它的优点是空间效率和查询时间都远远超过一般的加密算法，缺点是有一定的误识别率和删除困难。

一、Bloom-Filter加密算法的基本思想

Bloom-Filter加密算法的核心思想就是利用多个不同的Hash函数来解决“冲突”。

计算某元素x是否在一个集合中，首先能想到的方法就是将所有的已知元素保存起来构成一个集合R，然后用元素x跟这些R中的元素一一比较来判断是否存在亍集合R中，我们可以采用链表等数据结构来实现。但是，随着集合R中元素的增加，其占用的内存将越来越大。试想，如果有几千万个不同网页需要下载，所需的内存将足以占用掉整个迚程的内存地址空间。即使用MD5、UUID这些方法将URL转成固定的短小的字符串，内存占用也是相当巨大的。

亍是，我们会想到用Hash table的数据结构，运用一个足够好的Hash函数将一个URL映射到二迚制位数组，位图数组，中的某一位。如果该位已经被置为1，那么表示该URL已经存在。 Hash存在一个冲突，碰撞，的问题，用同一个Hash得到的两个URL的值有可能相同。

为了减少冲突，我们可以多引入几个Hash，如果通过其中的一个Hash值我们得出某元素不在集合中，那么该元素肯定不在集合中。只有在所有的Hash函数告诉我们该元素在集合中时，才能确定该元素存在亍集合中。

二、Bloom-Filter加密算法的基本特征

(1)存在一定错误率，发生在正向判断上（存在性），反向判断不会发生错误（不存在性）；

(2)错误率是可控制的，通过改变位数组大小、hash函数个数或更低碰撞率的hash函数来调节；

(3)保持较低的错误率，位数组空位至少保持在一半以上;

(4)给定m和n，可以确定最优hash个数，即k = ln2 * (m/n)，此时错误率最小；

(5)给定允许的错误率E，可以确定合适的位数组大小，即m >= log2(e) * (n * log2(1/E))，继而确定hash函数个数k；

(6)正向错误率无法完全消除，即使不对位数组大小和hash函数个数进行限制，即无法实现零错误率；

(7)空间效率高，仅保存“存在状态”，但无法存储完整信息，需要其他数据结构辅助存储；

(8)不支持元素删除操作，因为不能保证删除的安全性。

三、Bloom-Filter加密算法的优缺点

1、Bloom-Filter加密算法的优点

Bloom filte加密算法的最大优点是空间效率和查找时间复杂性，它的存储空间和插入/查询时间都是常数。Hash函数之间没有相关性，可以方便地由硬件并行实现。Bloom filter加密算法不需要存储元素本身，在某些对保密要求非常严格的场合有优势。另外，Bloom filter加密算法一般都可以表示大数据集的全集，而其它任何数据结构都难以做到。

2、Bloom-Filter加密算法的缺点

Bloom filter的缺点和优点一样显著，首先就是错误率。随着插入的元素数量增加，错误率也随之增加。虽然可以通过增加位数组大小或hash函数个数来降低错误率，但同时也时影响空间效率和查找性能，而且这个错误率是无法从根本上消除的。这使得要求“零错误”的场合无法应用Bloom filter加密算法。其次，一般情况下不能从Bloom filter加密算法中删除元素。一方面是我们不能保证删除的元素一定存在Bloom filter加密算法中，另一方面是不能保证安全地删除元素，可能会对其他元素产生影响，究其原因还是hash函数可能产生的碰撞造成的。

四、Bloom-Filter加密算法的应用

Bloom-Filter加密算法一般用于在大数据量的集合中判定某元素是否存在。例如邮件服务器中的垃圾邮件过滤器。在搜索引擎领域，Bloom-Filter加密算法最常用于网络蜘蛛(Spider)的URL过滤，网络蜘蛛通常有一个URL列表，保存着将要下载和已经下载的网页的URL，网络蜘蛛下载了一个网页，从网页中提取到新的URL后，需要判断该URL是否已经存在亍列表中。此时，Bloom-Filter加密算法是最好的选择。

小知识之URL映射

URL映射就是把URL转到另一个URL上面，这个功能一般是由WEB服务器来完成的。

TAG：

上一篇 : LTE无线移动通信系统加密算法的验证方法

下一篇 : 基于魔方变换的图像加密算法

文章标签

文档加密软件

文档信息安全管理软件

上网行为管理软件

应用程序管控软件

敏感文件管理软件

U盘设备管控软件

文件分发软件

IT资产管理软件

电脑操作记录软件

远程控制软件

聊天管控软件

敏感信息报警

屏幕管控

内网管理

深度行为分析

电脑屏幕录像

实时管控

补丁管理

网络准入控制管理系统