基于Paillier公钥密码体制的低频分词密文索引方案

廖祥宇，郑明辉，朱小强

(湖北民族大学 信息工程学院，湖北 恩施 445000)

随着计算机的飞速发展，越来越多的人将资源放置数据库中[1]，同时为了敏感数据的安全性，许多人都会将明文进行不同程度的加密，虽然能在一定程度上保证自身敏感数据不被窃取，但也极大地降低了密文检索时的效率，不能满足现在高效率的需求.2012年李向前等[2]提出了Blum-Goldwasser概率密码体制的一种改进方案，降低了密文的膨胀率问题.2014年陈成钢[3]提出了一种确定的背包公钥密码体制的破译算法，利用公开密钥的超可达性，直接由公开密钥破译得到解密密钥，从而达到破译密文的目的.常见的数据库数据索引可以分为以下4类：① 基于文件的索引技术.经典算法有DES、AES[4]等算法.这种索引方法相对简单,但是缺点是这种方法需要是将全部文件进行搜索匹配，检索速率低，不适合大数据的数据库.② 基于记录的索引技术.相比于打包式的检索，该技术有了显著的提高.然而缺点就是用户仅针对某条记录中的某个字段检索时，必须对整条记录进行检索处理.③ 子密钥索引技术.由David等[5]提出，理论基础是中国的剩余定理[6],解决了检索时对整条记录检索的缺陷.然而，缺陷就是检索时需要对每条记录生成索引，过程烦琐.④ 基于全字段的索引技术.由于其粒度好，适应性和灵活性都比前者好很多.但是其缺点是其检索的基本单位是数据段，每一个字段都有一个索引，若是有M条记录，每条记录有N个字段，当M和N都很庞大的时候，检索某一字段时也需要M×N的时间，检索的效率反而降低了.

以上4种常见的数据库索引技术都实现了对数据的检索，但是都有一个共同的缺点就是不能较灵活、快速地对数据进行检索以提高效率.为克服上述方案的不足，提出了一种基于Paillier算法[7]的低频分词密文检索技术(a low frequency ciphertext retrieval technique based on paillier algorithm，LFPR)，该方案在保证满足用户检索需要的同时，能有效提高密文的检索效率.

图1 整体流程Fig.1 Overall flow chart

表1 低频分词top10Tab.1 Top10 low-frequency segmentation words

表2 表Ti的存储格式Tab.2 Storage format of table Ti

1 基于Paillier算法的低频分词密文检索算法

在方案提出之前，首先利用Jieba分词技术[8]将明文m按段落进行分词操作，利用权重选取出频率最低的10个分词，根据实际需要选择其中一个分词，作为后续的索引；然后利用Utf-8将汉字明文转码变成字符串类型并通过Paillier算法将转码后的数据进行加密得到密文Cipertext；最后将密文数据存放至数据库YmSql中，形成表结构并通过最初确定的分词建立索引，实现快速检索.整体流程图如图1所示.

1.1 预备知识

1) Jieba分词技术.Jieba分词技术是针对中文的概率语言模型分词，其本身具有一个名为dict.txt的词典，该词典拥有20 000多个中文字词，每一个字词都有根据训练语料统计的词频和词性.该技术涉及Trie树[9]、有向无环图(DAG)[10]、动态规划、隐马尔可夫模型(HMM)[11]以及维特比(Viterbi)等多种算法[12].由自带dict.txt的词典生成Trie树实现高效率的词图扫描，将所有可能的切分情况构建有向无环图(DAG)；由生成的DAG计算最大概率，动态规划查找最优路径，得到基于词频的最优分词组合；对于dict.txt词典没有登记的词，采用隐马尔可夫(HMM)模型来预测分词.

2) Utf-8编码.Utf-8是PowerBuilder的函数，该函数将数据字符串转换为Utf-8编码，并返回编码后的字符串，利用该函数将汉字转码为相对应的字符串，最后利用Paillier算法将转码后的明文数据进行加密.

3) Hash散列函数.Hash散列函数就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值，不同的输入其散列的值也不相同，具有唯一性.

1.2 低频分词的选取

首先Jieba算法将明文进行分词操作，利用权重计算选取出频率最低的10个分词，结果如表1所示.根据实际需要选择其中一个分词作为该段的索引，同时确保每段选取的都不相同，这样既保证了选取的分词是出现频率最低的且选择的分词具有唯一性，最后通过分词索引找到的段落也具有唯一性.测试明文链接为：http://cpc.people.com.cn/xuexi/n/2015/0717/c397563-27322232.html.

1.3 基于Paillier算法的明文加密

1.4 建立数据库表字段及索引

完成全部数据的加密后，将加密后的数据导入数据库中.首先为了保证数据解密后的自然语言是完整且正确的，将数据以自然段落划分为标准生成表字段，根据明文自然段的多少确定表字段T1,T2,…,Tn(1≤i≤n)，每一个表字段中都有Snumer、Scipertext、Shash三列组成，其中Shash是每个汉字出现的位置编号；Scipertext是通过Paillier算法加密得到的密文；Shash是Snumber和Scipertexi相加计算的结果，并将Shash作为索引值，每张Ti表只有一个Hi作为该表的索引.假设n=517，g=123,r=59.则加密后的数据库存储表Ti结构如表2所示.

2 实验仿真

借助PyCharm开发环境和Mysql2008R2数据库环境，采用文章所提出的检索算法对密文数据进行检索并与经典的AES算法和全字段加密算法对比.

图2 检索结果Fig.2 Retrieval results

图3 解密结果Fig.3 Decryption results

图4 字数对检索时间的影响Fig.4 The influence of word count on retrieval time

2.1 检索结果验证

通过对建立的索引进行查询，查询结果如图2所示.通过查询结果可以看出，通过索引Hi查询，可以直接定位到密文所在的位置，因为Hi是Hash索引的结果，根据Hash散列函数的特性可以确定该索引结果是唯一的，通过Snumber将密文按顺序排序，利用n解密密文得到Utf-8，最后Uif-8将转码为明文m，解密结果如图3所示.综上，该的检索技术是可以实现并且检索结果具有唯一性.

2.2 字节长度与检索时间

在搭建好的实验环境下，通过输入不同字节的数据，对密文检索时间进行对比验证，得到字节长度与检索时间之间的关系，如图4所示.

测试数据选取了100、500、1 000三个密文字数节点进行测试，通过图4可以看出，在密文字数较少时，检索速率较快，但随着密文字数增多，检索的时间也随之增加；密文字数在500字以内时，检索时间大致相同，但随着密文字数的不断增加，本文算法的检索时间较其他两种算法的检索时间有明显的提高.密文长度越长，密文的检索时间也会相应地增加.

3 结论

提出了一种基于Paillier公钥密码体制在数据库的改进与分析的算法，首先将Paillier算法、Jieba算法、Hash算法和数据库索引技术有效结合，利用Paillier算法对整个明文进行加密操作，利用p,q大素数的乘积n确保数据的安全性，然后结合Jieba算法和算法得到低频分词作为索引，最后将密文存储在数据库中，利用索引查询密文.实验结果表明，本文提出的算法能够有效地增加数据在数据库中的安全并且降低了在数据库中对整个密文进行检索，提高了检索效率.该算法的不足之处在于:当检索内容过长时，运行时间明显变长，只能应用于字段较少的内容.该问题是以后研究的重点.