基于Bloom Filter的密文检索改进方案

2016-08-16钱圣福朱王小江

中国科技信息 2016年9期

钱圣福朱王小江

钱圣福朱王小江

基于Bloom Filter传统的密文检索存在较大的误检率的问题，这严重影响了密文检索结果的准确性，本文中，通过引入唯一向量，对Bloom Filter的基础数据结构进行了改造，使其在不明显增加索引大小的前提下，改善误检率。通过在创建索引和构造陷门的过程中引入非对称加密机制，使得新算法能够有效抵抗相似性统计分析攻击，并且不会泄露任何用户信息和档案明文信息。通过一系列实验对改进系统进行了安全性、效率等方面的对比，该系统在保证高检索效率的同时，能够达到较高的安全等级。

研究内容

密文检索技术的核心在于保证数据安全性的前提下，对密文实现快速检索，即实现密文对密文的检索，涉及的核心技术主要包括索引的创建、更新、删除、检索，索引和文档的安全性以及密钥管理。1992年，Ostrovsky最早提出了这一问题的解决方案，1996年Goldreich和Ostrovsky又对这一方案进行了改进。2000年，此科研团队又在原方案的基础上提出了一种新的对称加密可搜索方案SSKE。Dan Boneh提出了一种基于公钥密码系统的密文检索机制（PEKS，Public Encryption with Keyword Search）。Yan－ Cheng Chang和Michael Mitzenmacher等人提出了一种基于安全索引的密文全文检索方案，实现方法是在文档加密前提取关键词建立相应的安全索引，搜索时利用陷门对密文索引进行检索查询。这种方案能够实现在不对存储文档进行解密的前提下对密文进行检索。Dawn Xiao Song等人提出了一种实现密文对密文检索的查询方案，主要方法是利用序列加密算法对文档进行处理，检索时只需要将关键词于密文文本中的加密词语进行匹配即可实现检索。Eu－Jin Goh等人提出了一种能够一定程度上隐藏用户访问模式（Access Patterns）的对称可搜索加密算法，此方案利用Bloom过滤器来构建密文索引，索引与加密文档在语义上是完全无关的，并且检索算法时间复杂度为O（1）。另外国内也在此领域做了不少研究工作。

本文主要工作如下：1）高效的安全索引结构。基于为随机函数和布隆过滤器的密文检索模型，针对理论架构和原方案较高的差错率和较低的安全性进行改进，在保证安全性和检索效率的同时，实现了检索结果的零差错反馈。2）密文检索原型系统的设计与实现。设计并且实现了一个基于Bloom Filter安全索引的密文全文检索的原型系统，并对该系统的重要组成部分给出了结构框图。

基于Bloom Filter的密文检索改进方案

索引构造过程改进

通过对GOH等人提出的基于BloomFilter的密文全文检索方案的分析，对原方案的改进，引入一个加密向量，该向量的第i位置1，其余位置0，每一个加密向量对应文档Di中的单词Wi。改进后的索引构建流程如图1所示。

陷门构造改进

传统方案采取直接对关键词进行散列化的方式生成关键词陷门，关键词W的陷门Tw直接使用密钥Kpriv与明文W进行散列化后生成，这样会使得不同文章中相同关键词所生成的陷门完全相等，这样就暴露了用户的访问模式（Access Patterns），即两次搜索的关键字相同，这样就使得索引面临着相似性统计分析攻击的危险，针对这一点，对陷门生成过程进行了改进。在S－INX中，陷门不仅仅跟密钥和关键词相关，还引入了关键字在对应文档中的相对位置和频率信息，改进的关键词陷门生成过程如图2所示。

如图所示，S－INX的陷门引入了一个表征单词唯一性的特征向量Zj。改造后的陷门实现了对用户模式的隐藏，这时候属于不同文档的相同单词所构造的陷门就不可能相同。由于索引每个文档的一一对应，因此在检索时需要对每一个索引进行查询，后面会有详尽的性能分析。

检索过程的改进

通过对原方案的分析研究，当接到查询关键字W的时候，首先生成陷门，然后将其散列化后与Bloom Filter中的相应数据位进行比对，如果所有位置上的值都是“1”，则表示该关键字在索引中，如果有一个位置是“0”，就表示该关键字不在索引中。这种算法使得索引容易遭受到相似度分析。

图1 S－INX的索引构建方案

当查询请求为关键字y1时，首先按照改进陷门构建方案生成对应陷门，接着对y1生成特征向量v1，然后根据对y1生成的Bloom Filter位置值，对相应位置的特征向量链表做∩操作，如果结果为v1，则说明y1在索引中，也即关键词w在文章D中，结果为空则表明该索引不含有关键词w。当查询请求为关键字y1时，首先按照改进陷门构建方案生成对应陷门，接着对y1生成特征向量v1，然后根据对y1生成的Bloom Filter位置值，对相应位置的特征向量链表做∩操作，如果结果为v1，则说明y1在索引中，也即关键词w在文章D中，结果为空则表明该索引不含有关键词w。

高效的安全索引结构设计与实现

具有高安全性和良好检索性能的索引结构是密文检索系统的核心部分。为了满足这样的要求，实现索引与文档加密方式按需动态配置，此原型系统将索引和文档的加密过程分开、独立进行，索引数据和文档的安全性完全取决于所选择的加密算法的安全性。索引结构本身的安全性又对索引中存储的数据的安全性至关重要，因而索引的安全性在密文检索模型整体安全性上位置突出，需要加强保护。

S－INX安全索引结构的设计

S－INX索引文件的主要结构如图3。本系统的索引文件主要由4个部分组成：con文件，in文件，doc文件，seg文件。这四个文件包含了与索引处理有关的所有必要信息。其中，con文件存储的是整个索引文件的核心部分，包含了与创建索引有关的所有关键信息，包括用于伪随机函数的安全参数，它是体现所生成的哈希值散列性的关键，对于减少过滤器中链表长度有直接作用，还包括索引所含文档数，doc文件长度，in文件长度，其中的文档seg号，将文档和对应索引一一对应起来，是能够进行正确索引的关键，对其他三个文件的长度现在也在相应参数中一一体现；seg文件负责存放被索引后的文件的内容，包含了文档所有域的内容。由于索引文件大小的限制，在应用中会对seg文件进行分块，此文件所包含的域权值、域是否标识化是影响索引准确率的关键因素，可以根据实际需要动态调整。Doc文件负责文档内容的存储，包括文档的唯一识别ID，这是索引与文档对应以及返回检索结果的关键参数，文档所包含的域数也指明了文档能够被分割的最大域数的限制，因为过多的域数会导致检索效率的直线下降。in文件存储了Bloom Filter的相关数据结构，是执行构建索引和检索匹配操作的关键，对应各个文档所关联的Bloom Filter内容。单个Bloom Filter数据结构是一个存储链表的数组。当接收到一个查询请求时，根据con文件中的BF在in文件中的相对偏移量找到对应的Bloom Filter数组，执行∩操作。

S－INX结构实现

图2 S－INX的陷门构建过程

图3 S－INX索引文件结构

S－INX结构的实现包括三个接口和一个实现类，包括inxINT，fileReadINT，anaINT，以及inxIMPL，第一个接口完成索引上传和更新等与索引有关的功能，第二个结构实现对文档的读操作，第三个结构实现按照分析规则对文档内容进行提取，它有几个实现类，以针对不同的文件格式，包括docxIMPL，csvIMPL，txtIMPL，pdfIMPL，这里仅列出主要文件的实现类，可以根据实际需要添加其他的文件读取实现类。当用户将需要建立安全索引的文档进行上传操作时，fileReadINT接口负责提取文档信息，包括文档ID，文档内容等。然后调用normalize（）方法对所有格式文档进行统一化处理，并生成统一格式的对象Document。接着inxINT调用其中的Index（）方法对生成的Document对象进行索引生成。在进行索引创建的时候，需要调用anaINT对文档进行分词，这里的采用Lucene的文档分析器执行相应操作，分析规则和分析语言可以根据实际需要动态调整，其中的analysis（）主要负责分词工作。

系统实现及分析

系统架构

图4 密文检索系统架构

整个系统共分为四个组成部分：1）文档分析；2）构建安全索引；3）文档加密；4）检索查询。明文文档经过结构化处理以及经解释器分词以后，然后使用用户的密钥对文档进行加密并将加密后的文档上传至云服务器；分词完成后，对关键词进行过滤，去掉重复的单词以及停用词，使用剩下的不重复词语生成陷门并构建索引，将陷门上传至服务器；检索时，用户先用自己的密钥对关键词进行加密生成陷门以后，将陷门传送至服务器以便索引，并遵循访问控制等控制机制的限制获取密文文档存储位置信息。这其中为整个系统安全保驾护航的就是密钥管理模块。该模块提供文档加密、索引建立、检索查询过程的密钥生成、销毁及管理服务。

系统IO性能测试

主要测试对文档长度对系统输入输出能力的影响，实验样本为不同字节长度的文档，为了反应文件格式对IO性能的影响，选取了三种不同的文档类型，包括DOCx格式的文档，PDF格式的文档，TXT格式的文档以及RTF格式的文档，文档长度选取了七个值，1KB、32KB、128KB、512KB、1MB、8MB、32MB，这样的取值是文档大小形成了类均匀分布，能够很好的反应文档长度与系统输入、输出性能的关系。测试的主要指标有文档分析所耗时间、构建索引所耗时间、加密文档所耗时间、解密文档所耗时间，并给出了对实验结果的分析。DOCx文件、PDF文件和RTF三种格式的文件在各项参数的表现都比较平均，也就是说，这三种文件格式对系统输入、输出性能的影响不是很明显，相比而言RTF文件格式对系统性能影响最小，系统的所耗时间随着文件字节长度的增加而增加。从加密文件耗时和解密文件耗时来看，RTF格式文件由于其文件格式简单，头文件信息较少，因而在加、解密所耗时间这一指标上表现最好，TXT文件次之，其次是PDF文件，而DOCx文件由于其除去文档内容以外的控制信息较多，因而其文件格式对加解密这一项性能指标影响较大。由于文件分析采用的Lucene中文分词器CnTokenizer采用二元覆盖方式实现中文分词，因而TXT这种格式性不强的文件在文件分析阶段所耗的时间最多。综合所有性能指标来看，RTF文件对系统的输入、输出性能影响最小。

安全索引检索误检率性能测试

针对原方案Z－IDX高误检率的问题，本实验旨在对比测试传统倒排索引、Z－IDX、S－INX三种方案检索返回结果的正确率，本测试选取了10个常用汉语词语，文件集合为包含了10000个中文文档的大型文件集，格式均为TXT，主要测试结果为输入相应关键词返回的正确结果的情况，具体实验数据如表1所示。

表1 不同索引结构误检率性能测试

实验结果表明，本文所改进的方案S－INX已经能够实现检索结果零误检。

结语

本文着眼于当前云存储技术在发展中遇到的一系列亟待解决的安全问题，设计并实现了一个基于布隆过滤器的安全索引密文全文检索原型系统，改进了基于布隆过滤器的安全索引构建方案，设计并实现了基于安全索引的密文全文检索原型系统，对改进模型的性能进行了实验分析。结果表明，改进方案S－INX在检索大型文档集合时效率和准确率都在对比方案中获得较大提升。