周勇， 翁锟源， 程航， 严娜招， 黄芹健

(福州大学数学与统计学院， 福建 福州 350108)

0 引言

PDF是一种用独立于应用程序、 硬件、 操作系统的方式呈现文档的文件格式. 日常所使用的PDF软件， 除了浏览的功能以外， 通常还会对PDF进行一些操作， 比如合并. 传统的PDF合并往往需要专业的文档编辑软件， 比如Adobe Acrobat软件， 其可提供线下手动合并功能， 但随着云计算技术的快速发展以及大数据时代的到来， 服务线上外包已成为一种趋势， 其功能的丰富性和适用性并不是传统线下服务所具备的. 近年来， 线上合并服务也相继出现， 如金山PDF付费订阅服务可提供在线PDF合并的功能， 也有免费提供在线合并PDF功能的网站， 如PDF转换器， 但这种基于第三方的服务往往不可信任， 可能存在数据隐私泄露问题. 另外， 存储和编辑PDF文档往往需要用户手动逐一打开PDF文件对其内容相关性进行主观判定， 然后根据判定结果决定是否合并. 显然， 这种人工合并的方式既费时又费力， 无法满足用户对海量PDF文件在线精准、 高效、 自动合并的需求. 借助当下蓬勃发展且具有强大计算力的云计算技术， 可实现海量PDF文件自动合并服务的外包， 给用户带来极大的便利， 但同样存在文件内容泄露的风险， 无法完全消除用户对数据安全和个人隐私的担忧[1-2]. 因此， 在保护用户数据隐私同时实现PDF文件云外包自动合并具有重大现实意义.

目前， 云外包数据安全处理已得到众多企业、 专家和学者的普遍关注， 相继也出现不少相关的研究成果， 如密文域文本/图像检索[3-5]、 密文域可逆信息隐藏[6-7]、 密文域监控视频处理[8-9]等， 但国内外关于PDF文件安全外包合并的研究几乎空白. 文献[10]利用Shamir秘密分享技术(shamir’ s secret sharing, SSS)[11]提出一种基于在线免费文件合并网站对PDF文件进行安全合并的方案. 利用该方案， 用户无需担心隐私泄露, 只要将明文数据的秘密分享分发给指定的不同服务器， 具体合并操作由服务器端来完成， 但其人工确定待合并文件的方式并不适合如今数据爆炸的信息时代. 然而， 文献[10]并未解决相似PDF自动合并这个能给用户带来现实便利的问题.

为了解决以上问题， 本研究提出一种新的面向隐私保护的相似PDF文件外包自动合并方法. 首先， 用户采用局部敏感哈希(locality sensitive hash)[12]中Simhash算法[13]在本地提取PDF文件的特征信息， 将高维的特征向量映射成低维的特征向量. 然后， 利用基于中国剩余定理(chinese remainder theorem， CRT)秘密分享技术[14]对特征向量进行加密， 并上传给计算服务器. 最后， 联合计算服务器和数据服务器计算出PDF文件间的相似性， 根据用户的需求返回合并后的密文PDF文件， 由用户解密恢复出明文合并后的PDF文件. 具体而言， 主要的贡献如下：

1)利用秘密分享技术设计一种相似PDF文件外包自动合并的方案. 使用该方案， 服务器在不知道明文内容情况下， 仍可以合并相似的密文PDF文件；

2)设计一种哈希码加密方法， 可在确保数据隐私的情况下， 实现PDF文件相似性的安全计算；

3)本研究所提方法并不局限于单个用户使用， 可扩展到多用户的场景.

1 背景与预备知识

1.1 PDF结构和解析

本研究的操作对象是PDF文档， 需要解析PDF文档以及提取PDF文本. 其中， PDF文档结构如图1所示， 该树形结构反映了PDF文件体中各个间接对象之间的层级关系， PDF文档的根对象(Catalog)对应的是图中树的根节点， 根对象包含页根对象和大纲， 作为PDF主要组成部分的页根对象包含了PDF文件中可视内容中的文本、 图形、 图像内容.

图1 PDF文档结构Fig.1 Structure of PDF files

根据PDF文档结构的特点， 可以从根对象出发， 依据交叉引用表对PDF进行解析， 得到一个包含文本信息、 色彩空间、 图形、 图像等信息的内容流(其实， 内容流包含一系列的操作符)， 然后就可以在这个内容流中利用文本对象相关的操作符， 即可提取PDF文档中的文本内容[15].

1.2 秘密分享技术

本研究所采用的(k,n)-CRT秘密分享算法如下：

假定{a1,a2, …,an}是秘密信息a的n个分享， 且满足：

ai=amodmi

(1)

其中， {m1,m2, …,mn}是一个两两互素的集合.

根据(k,n)-CRT的分享机制， 仅通过k个分享就可重建秘密信息a， 即：

(2)

注意， 如果获得超过k个分享， 并不妨碍秘密信息的重构， 但少于k个分享， 原始秘密信息将无法重构.

2 研究方法

如图2所示， 所提安全合并方案包含三个参与方： 用户、 计算服务器和数据服务器. 用户负责提取和加密PDF文件特征向量， 并将密文特征向量和PDF文件分别上传给计算服务器和数据服务器. 此外， 用户在密钥帮助下能够解密返回的密文合并PDF文件， 以获得相应的明文PDF文件； 计算服务器除了为用户的特征向量分享提供存储空间， 还具有计算特征向量分享间的模数加法能力， 并能将计算结果提交给数据服务器； 数据服务器能够为用户提供密文PDF文件存储服务， 同时也为用户提供PDF文件安全相似度计算， 并依据用户请求信息返回合并后的密文PDF文件.

图2 本研究所提方案的流程图Fig.2 The flow chart of the proposed scheme

2.1 特征提取

算法1文本提取输入: 待处理的PDF文本P1, P2, …, Pm输出: 提取出的文本T1, T2, …, Tm1. For 每个PDF文档2. For PDF文档的每个页面3. 提取页面的全部元素4. If 元素是文本5. 保存文本到Ti6. EndIf7. EndFor8. EndFor 每个文档

特征提取包含两部分工作： 文本提取和Simhash生成. 首先从PDF文件中提取文本， 如1.1节所述， PDF的文本内容是以对象的形式嵌入， 这里使用第三方jieba库来提取PDF文档中的文本， 具体如算法1所示.

当完成文本提取后， 接着执行Simhash生成. 与传统的哈希算法最大的区别在于： Simhash能够确保相似数据具有相似的哈希值. 借助该算法， 可以将特征向量从高维空间映射到低维空间， 有利于海量数据的快速匹配. 利用Simhash算法计算出每个PDF文件的相似哈希值. 具体流程如下：

① 初始化. 输入PDF文档， 输出等位长的Simhash码H和向量V， 均初始化为零向量；

② 分词、 过滤. 使用jieba分词库将文档进行分词， 使其转化为一组文本特征， 并将无意义的组词、 语气词等过滤；

③ 加权哈希. 计算每个词的哈希值α， 依据当前词的重要性计算其相应权重， 若α的第i位为1， 则在V的第i位加上该词的权重， 否则减去.最后得到向量V；

④ 二进制化.观察向量V， 若第i位元素大于0， 则H的第i位设为1， 否则为0.

2.2 数据加密

为了保护数据的安全， 需要加密PDF文件和Simhash码. 对于PDF文件的安全， 用户直接采用传统的AES对称加密方法对文本内容进行加密(PDF文件中的操作符不做加密处理)， 并上传给数据服务器进行存储. Simhash码含有PDF文件的文本信息， 是实现文件间相似性计算的关键， 其隐私安全保障将采用如下维度扩展、 随机置乱、 奇偶替换、 比例伸缩和CRT秘密分享相结合的方式：

Ⅰ) 将Simhash码H进行维度扩展， 增加指定数目的值为零的位；

Ⅱ) 随机置乱维度扩展后的Simhash码H′的位元素， 记为H″；

Ⅲ) 在一定范围内随机选择正奇数/偶数替换H″中元素1/0， 设修改后Simhash码为H‴；

Ⅳ) 利用式子u·s+ε对H‴中每个元素u进行s比例伸缩， 并利用均匀随机分布噪声ε进一步扰乱, 这里ε满足ε～U(0,γ),γ≤s;

Ⅴ)经过以上四个修改步骤后， 用户利用公式(1)将新的Simhash码加密成n个分享， 分别发送给云端计算服务器进行存储和后续模和计算.

2.3 安全合并

PDF文件云外包安全相似合并关键在Simhash码的汉明距离安全计算， 其由合并请求、 模和计算及相似合并三个算法构成.

合并请求. 如果想从云端PDF数据库(即由存储在数据服务器上的密文PDF文件所构建的库)合并所需的PDF文件， 用户仅需要提交一个查询PDF文件的Simhash码， 简称Simhash查询码， 其加密方式如2.2节中Simhash码加密方法. 为了便于后续说明， 假设经过四个修改步骤后的Simhash查询码为Hq， 其n个分享为{Hq, 1,Hq, 2, …,Hq, n}， 则Hq第t个元素的第j个分享为：

Hq, j(t)=Hq(t)modmj

(3)

为了减少通信开销， 用户只需从n个分享中随机抽取k个分享分别发送给计算服务器， 以此激活相关服务器进行后续计算， 无需额外计算请求开销.

模和计算.假设第j个计算服务器被激活， 则其将逐一执行查询特征与存储在计算服务器数据库PDF文件特征之间的模和运算：

Sum(Hq, j,Di, j)=(Hq, j+Di, j)modmj

(4)

即

Sum(Hq, j,Di, j)={(Hq, j(t)+Di, j(t))modmj}1≤t≤τ

(5)

其中：τ表示Hq的维度；Di, j表示第i个数据库Simhash码的第j个分享.

随后， 计算服务器将所有的Sum(Hq, j,Di, j)(1≤i≤l)， 发送给数据服务器.由于哈希码Hq与Di之间和的重建是在数据服务器上执行， 因此根据CRT秘密分享技术的特点， 任意第j个计算服务器无法从Sum(Hq, j,Di, j)中推测出原始Sum(Hq,Di).

算法2 相似合并输入: Simhash码和分享输出: 合并后密文PDF1. For 每个Simhash码的和分享2. 重建Simhash码间的和3. 计算出汉明距离4. EndFor5. If 汉明距离小于预定值6. 合并并返回PDF7. EndIf

具体相似合并过程如算法2所示.

3 实验结果与分析

在实验中， 使用一台8 GB 内存、 Intel(R) Core(TM) i5-7500 CPU的一体机， 采用(3, 5)-CRT秘密分享技术， 即选取k=3,n=5， 对外包安全合并中四个不同算法： 合并请求、 模和计算、 数据库Simhash码加密、 相似合并进行计算开销对比实验， 对应的两两互素的集合是{29, 31, 37, 41, 43}， 伸缩因子s=47， 随机噪声ε<47， 代码使用Matlab语言编写. 理论上，k,n(k

通常在计算机视觉领域， 高维度的特征具有更优异的辨别力， 往往能带来更高的性能， 但也要付出更多的计算代价. 如图3(a)所示， 随着Simhash码维度增加， 合并请求就需要花费更多的计算时间. 相对来说， 合并请求算法的时间开销比较小， 比如维度为1 024时， 其计算时间仅为0.070 6 ms， 这主要是因为合并请求算法仅需加密一个Simhash查询码. 为了测试PDF文件数目对所提方案中模和计算/数据库Simhash码加密/相似合并算法计算开销的影响， 选取5个数量不同PDF文件数据集进行实验， 结果如图3(b)～(d)所示. 在给定维度情况下， 这三个算法的计算开销与数据集大小成正比， 所含文件越多计算开销越大. 比如给定特征维度为64， 当PDF文件数目为100和500时， 模和计算/数据库Simhash码加密算法所对应的运行时间分别为1.27/4.70 ms， 6.17/24.33 ms， 而相似合并算法对应的时间开销分别为1.52、 7.82 s. 在同等条件下， 相似合并算法的开销最大， 易导致响应延迟， 从而影响用户的体验. 相似合并算法较高计算开销除了CRT重建秘密算法自身的原因外， 在一定程度上与所采用的单线程且过程非优化的编程语言有关， 但无论如何对于具有海量计算能力的云服务器来说， 这个算法很容易在云端被高效执行. 同时， 从图3(b)～(d)中也发现在同等大小数据集下， 模和计算/数据库Simhash码加密/相似合并算法效率会随着特征维度的增加而降低. 为了完善实验结果， 并进一步测试外包安全合并中四个不同算法与PDF文本数量的关系， 在另外3个数据量更大的数据集(即数据量为4 000， 8 000， 10 000个)上进行测试， 实验结果(Simhash码长度设置128， 其他参数设置保持不变)如表1所示， 其结论与上述实验保持一致. 其中， 合并请求计算开销跟数据集大小无关， 故保持不变.

(a) 合并请求算法计算开销

(b) 模和计算算法计算开销

(c) 数据库Simhash码加密开销

表1 不同算法计算开销对比

为了展示计算服务器数量(对应就是CRT秘密分享技术中n的值)对不同算法的影响， 本文进行了相应的对比实验， 其中伸缩因子s=80， Simhash码维度为128， PDF文件数量设为100， 计算服务器数量分别为6， 8， 10台， 实验结果如表2所示. 显然， 当n增加时， 所有算法的开销均随之变大. 相对来说， 合并请求算法开销低于Simhash码加密和相似合并算法， 这主要因为其只需针对一个PDF文件特征操作. 同时本研究也发现： 模乘逆的操作使得相似合并算法的开销远大于Simhash加密与模和计算算法， 而模和计算仅牵涉到加法运算， 其开销低于拥有更多运算的Simhash加密算法.

表2 不同计算服务器数量下不同算法计算开销对比

除了文件数量和计算服务器数量对本研究所提方案性能有影响外， Simhash加密中u·s+ε式子也会增加方案整体的计算开销， 是影响系统性能的关键因素. 究其原因是以上四个算法都是在其基础上设计的， 但其噪声ε的随机性使得本研究所提方案安全性得以进一步提高， 甚至相同的明文可产生不同的密文， 使得特征向量每个元素的密文更加随机化.

为了验证文中提出方案在完成相似度判断和PDF文件合并的同时， 保证用户隐私不被泄露. 选取两个PDF文件进行实验展示. 图4显示在解密的情况下， PDF文件合并前后的效果. 表3表明： 在本地用户端可以得到完整的明文PDF文本信息； 经过加密处理后， 在没有密钥的情况下， 数据服务器是无法识别出其具体的内容.

图4 PDF文件合并前后的效果Fig.4 PDF file effect comparison before and after merging

表3 提取的文本在各参与方的表现形式

4 结语

提出一种基于Simhash的相似PDF外包安全自动合并方法. 该方案利用中国剩余定理来加密PDF文件的特征向量， 并构建汉明距离安全外包计算机制， 从而保证云端服务器在不知明文内容的情况下， 实现密文PDF文件的相似性计算和合并任务. 此外， CRT秘密分享技术也确保了PDF特征的信息理论安全， 其无密钥的特性使得方案天然可推广到多用户的场景. 未来的工作在于提高相似性准确度和系统运行效率， 并支持非PDF文件的外包合并.