周勇， 翁錕源， 程航， 嚴(yán)娜招， 黃芹健

(福州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 福建 福州 350108)

0 引言

PDF是一種用獨(dú)立于應(yīng)用程序、 硬件、 操作系統(tǒng)的方式呈現(xiàn)文檔的文件格式. 日常所使用的PDF軟件， 除了瀏覽的功能以外， 通常還會(huì)對(duì)PDF進(jìn)行一些操作， 比如合并. 傳統(tǒng)的PDF合并往往需要專業(yè)的文檔編輯軟件， 比如Adobe Acrobat軟件， 其可提供線下手動(dòng)合并功能， 但隨著云計(jì)算技術(shù)的快速發(fā)展以及大數(shù)據(jù)時(shí)代的到來(lái)， 服務(wù)線上外包已成為一種趨勢(shì)， 其功能的豐富性和適用性并不是傳統(tǒng)線下服務(wù)所具備的. 近年來(lái)， 線上合并服務(wù)也相繼出現(xiàn)， 如金山PDF付費(fèi)訂閱服務(wù)可提供在線PDF合并的功能， 也有免費(fèi)提供在線合并PDF功能的網(wǎng)站， 如PDF轉(zhuǎn)換器， 但這種基于第三方的服務(wù)往往不可信任， 可能存在數(shù)據(jù)隱私泄露問(wèn)題. 另外， 存儲(chǔ)和編輯PDF文檔往往需要用戶手動(dòng)逐一打開(kāi)PDF文件對(duì)其內(nèi)容相關(guān)性進(jìn)行主觀判定， 然后根據(jù)判定結(jié)果決定是否合并. 顯然， 這種人工合并的方式既費(fèi)時(shí)又費(fèi)力， 無(wú)法滿足用戶對(duì)海量PDF文件在線精準(zhǔn)、 高效、 自動(dòng)合并的需求. 借助當(dāng)下蓬勃發(fā)展且具有強(qiáng)大計(jì)算力的云計(jì)算技術(shù)， 可實(shí)現(xiàn)海量PDF文件自動(dòng)合并服務(wù)的外包， 給用戶帶來(lái)極大的便利， 但同樣存在文件內(nèi)容泄露的風(fēng)險(xiǎn)， 無(wú)法完全消除用戶對(duì)數(shù)據(jù)安全和個(gè)人隱私的擔(dān)憂[1-2]. 因此， 在保護(hù)用戶數(shù)據(jù)隱私同時(shí)實(shí)現(xiàn)PDF文件云外包自動(dòng)合并具有重大現(xiàn)實(shí)意義.

目前， 云外包數(shù)據(jù)安全處理已得到眾多企業(yè)、 專家和學(xué)者的普遍關(guān)注， 相繼也出現(xiàn)不少相關(guān)的研究成果， 如密文域文本/圖像檢索[3-5]、 密文域可逆信息隱藏[6-7]、 密文域監(jiān)控視頻處理[8-9]等， 但國(guó)內(nèi)外關(guān)于PDF文件安全外包合并的研究幾乎空白. 文獻(xiàn)[10]利用Shamir秘密分享技術(shù)(shamir’ s secret sharing, SSS)[11]提出一種基于在線免費(fèi)文件合并網(wǎng)站對(duì)PDF文件進(jìn)行安全合并的方案. 利用該方案， 用戶無(wú)需擔(dān)心隱私泄露, 只要將明文數(shù)據(jù)的秘密分享分發(fā)給指定的不同服務(wù)器， 具體合并操作由服務(wù)器端來(lái)完成， 但其人工確定待合并文件的方式并不適合如今數(shù)據(jù)爆炸的信息時(shí)代. 然而， 文獻(xiàn)[10]并未解決相似PDF自動(dòng)合并這個(gè)能給用戶帶來(lái)現(xiàn)實(shí)便利的問(wèn)題.

為了解決以上問(wèn)題， 本研究提出一種新的面向隱私保護(hù)的相似PDF文件外包自動(dòng)合并方法. 首先， 用戶采用局部敏感哈希(locality sensitive hash)[12]中Simhash算法[13]在本地提取PDF文件的特征信息， 將高維的特征向量映射成低維的特征向量. 然后， 利用基于中國(guó)剩余定理(chinese remainder theorem， CRT)秘密分享技術(shù)[14]對(duì)特征向量進(jìn)行加密， 并上傳給計(jì)算服務(wù)器. 最后， 聯(lián)合計(jì)算服務(wù)器和數(shù)據(jù)服務(wù)器計(jì)算出PDF文件間的相似性， 根據(jù)用戶的需求返回合并后的密文PDF文件， 由用戶解密恢復(fù)出明文合并后的PDF文件. 具體而言， 主要的貢獻(xiàn)如下：

1)利用秘密分享技術(shù)設(shè)計(jì)一種相似PDF文件外包自動(dòng)合并的方案. 使用該方案， 服務(wù)器在不知道明文內(nèi)容情況下， 仍可以合并相似的密文PDF文件；

2)設(shè)計(jì)一種哈希碼加密方法， 可在確保數(shù)據(jù)隱私的情況下， 實(shí)現(xiàn)PDF文件相似性的安全計(jì)算；

3)本研究所提方法并不局限于單個(gè)用戶使用， 可擴(kuò)展到多用戶的場(chǎng)景.

1 背景與預(yù)備知識(shí)

1.1 PDF結(jié)構(gòu)和解析

本研究的操作對(duì)象是PDF文檔， 需要解析PDF文檔以及提取PDF文本. 其中， PDF文檔結(jié)構(gòu)如圖1所示， 該樹(shù)形結(jié)構(gòu)反映了PDF文件體中各個(gè)間接對(duì)象之間的層級(jí)關(guān)系， PDF文檔的根對(duì)象(Catalog)對(duì)應(yīng)的是圖中樹(shù)的根節(jié)點(diǎn)， 根對(duì)象包含頁(yè)根對(duì)象和大綱， 作為PDF主要組成部分的頁(yè)根對(duì)象包含了PDF文件中可視內(nèi)容中的文本、 圖形、 圖像內(nèi)容.

圖1 PDF文檔結(jié)構(gòu)Fig.1 Structure of PDF files

根據(jù)PDF文檔結(jié)構(gòu)的特點(diǎn)， 可以從根對(duì)象出發(fā)， 依據(jù)交叉引用表對(duì)PDF進(jìn)行解析， 得到一個(gè)包含文本信息、 色彩空間、 圖形、 圖像等信息的內(nèi)容流(其實(shí)， 內(nèi)容流包含一系列的操作符)， 然后就可以在這個(gè)內(nèi)容流中利用文本對(duì)象相關(guān)的操作符， 即可提取PDF文檔中的文本內(nèi)容[15].

1.2 秘密分享技術(shù)

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

假定{a1,a2, …,an}是秘密信息a的n個(gè)分享， 且滿足：

ai=amodmi

(1)

其中， {m1,m2, …,mn}是一個(gè)兩兩互素的集合.

根據(jù)(k,n)-CRT的分享機(jī)制， 僅通過(guò)k個(gè)分享就可重建秘密信息a， 即：

(2)

注意， 如果獲得超過(guò)k個(gè)分享， 并不妨礙秘密信息的重構(gòu)， 但少于k個(gè)分享， 原始秘密信息將無(wú)法重構(gòu).

2 研究方法

如圖2所示， 所提安全合并方案包含三個(gè)參與方： 用戶、 計(jì)算服務(wù)器和數(shù)據(jù)服務(wù)器. 用戶負(fù)責(zé)提取和加密PDF文件特征向量， 并將密文特征向量和PDF文件分別上傳給計(jì)算服務(wù)器和數(shù)據(jù)服務(wù)器. 此外， 用戶在密鑰幫助下能夠解密返回的密文合并PDF文件， 以獲得相應(yīng)的明文PDF文件； 計(jì)算服務(wù)器除了為用戶的特征向量分享提供存儲(chǔ)空間， 還具有計(jì)算特征向量分享間的模數(shù)加法能力， 并能將計(jì)算結(jié)果提交給數(shù)據(jù)服務(wù)器； 數(shù)據(jù)服務(wù)器能夠?yàn)橛脩籼峁┟芪腜DF文件存儲(chǔ)服務(wù)， 同時(shí)也為用戶提供PDF文件安全相似度計(jì)算， 并依據(jù)用戶請(qǐng)求信息返回合并后的密文PDF文件.

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

2.1 特征提取

算法1文本提取輸入: 待處理的PDF文本P1, P2, …, Pm輸出: 提取出的文本T1, T2, …, Tm1. For 每個(gè)PDF文檔2. For PDF文檔的每個(gè)頁(yè)面3. 提取頁(yè)面的全部元素4. If 元素是文本5. 保存文本到Ti6. EndIf7. EndFor8. EndFor 每個(gè)文檔

特征提取包含兩部分工作： 文本提取和Simhash生成. 首先從PDF文件中提取文本， 如1.1節(jié)所述， PDF的文本內(nèi)容是以對(duì)象的形式嵌入， 這里使用第三方j(luò)ieba庫(kù)來(lái)提取PDF文檔中的文本， 具體如算法1所示.

當(dāng)完成文本提取后， 接著執(zhí)行Simhash生成. 與傳統(tǒng)的哈希算法最大的區(qū)別在于： Simhash能夠確保相似數(shù)據(jù)具有相似的哈希值. 借助該算法， 可以將特征向量從高維空間映射到低維空間， 有利于海量數(shù)據(jù)的快速匹配. 利用Simhash算法計(jì)算出每個(gè)PDF文件的相似哈希值. 具體流程如下：

① 初始化. 輸入PDF文檔， 輸出等位長(zhǎng)的Simhash碼H和向量V， 均初始化為零向量；

② 分詞、 過(guò)濾. 使用jieba分詞庫(kù)將文檔進(jìn)行分詞， 使其轉(zhuǎn)化為一組文本特征， 并將無(wú)意義的組詞、 語(yǔ)氣詞等過(guò)濾；

③ 加權(quán)哈希. 計(jì)算每個(gè)詞的哈希值α， 依據(jù)當(dāng)前詞的重要性計(jì)算其相應(yīng)權(quán)重， 若α的第i位為1， 則在V的第i位加上該詞的權(quán)重， 否則減去.最后得到向量V；

④ 二進(jìn)制化.觀察向量V， 若第i位元素大于0， 則H的第i位設(shè)為1， 否則為0.

2.2 數(shù)據(jù)加密

為了保護(hù)數(shù)據(jù)的安全， 需要加密PDF文件和Simhash碼. 對(duì)于PDF文件的安全， 用戶直接采用傳統(tǒng)的AES對(duì)稱加密方法對(duì)文本內(nèi)容進(jìn)行加密(PDF文件中的操作符不做加密處理)， 并上傳給數(shù)據(jù)服務(wù)器進(jìn)行存儲(chǔ). Simhash碼含有PDF文件的文本信息， 是實(shí)現(xiàn)文件間相似性計(jì)算的關(guān)鍵， 其隱私安全保障將采用如下維度擴(kuò)展、 隨機(jī)置亂、 奇偶替換、 比例伸縮和CRT秘密分享相結(jié)合的方式：

Ⅰ) 將Simhash碼H進(jìn)行維度擴(kuò)展， 增加指定數(shù)目的值為零的位；

Ⅱ) 隨機(jī)置亂維度擴(kuò)展后的Simhash碼H′的位元素， 記為H″；

Ⅲ) 在一定范圍內(nèi)隨機(jī)選擇正奇數(shù)/偶數(shù)替換H″中元素1/0， 設(shè)修改后Simhash碼為H?；

Ⅳ) 利用式子u·s+ε對(duì)H?中每個(gè)元素u進(jìn)行s比例伸縮， 并利用均勻隨機(jī)分布噪聲ε進(jìn)一步擾亂, 這里ε滿足ε～U(0,γ),γ≤s;

Ⅴ)經(jīng)過(guò)以上四個(gè)修改步驟后， 用戶利用公式(1)將新的Simhash碼加密成n個(gè)分享， 分別發(fā)送給云端計(jì)算服務(wù)器進(jìn)行存儲(chǔ)和后續(xù)模和計(jì)算.

2.3 安全合并

PDF文件云外包安全相似合并關(guān)鍵在Simhash碼的漢明距離安全計(jì)算， 其由合并請(qǐng)求、 模和計(jì)算及相似合并三個(gè)算法構(gòu)成.

合并請(qǐng)求. 如果想從云端PDF數(shù)據(jù)庫(kù)(即由存儲(chǔ)在數(shù)據(jù)服務(wù)器上的密文PDF文件所構(gòu)建的庫(kù))合并所需的PDF文件， 用戶僅需要提交一個(gè)查詢PDF文件的Simhash碼， 簡(jiǎn)稱Simhash查詢碼， 其加密方式如2.2節(jié)中Simhash碼加密方法. 為了便于后續(xù)說(shuō)明， 假設(shè)經(jīng)過(guò)四個(gè)修改步驟后的Simhash查詢碼為Hq， 其n個(gè)分享為{Hq, 1,Hq, 2, …,Hq, n}， 則Hq第t個(gè)元素的第j個(gè)分享為：

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

(3)

為了減少通信開(kāi)銷(xiāo)， 用戶只需從n個(gè)分享中隨機(jī)抽取k個(gè)分享分別發(fā)送給計(jì)算服務(wù)器， 以此激活相關(guān)服務(wù)器進(jìn)行后續(xù)計(jì)算， 無(wú)需額外計(jì)算請(qǐng)求開(kāi)銷(xiāo).

模和計(jì)算.假設(shè)第j個(gè)計(jì)算服務(wù)器被激活， 則其將逐一執(zhí)行查詢特征與存儲(chǔ)在計(jì)算服務(wù)器數(shù)據(jù)庫(kù)PDF文件特征之間的模和運(yùn)算：

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個(gè)數(shù)據(jù)庫(kù)Simhash碼的第j個(gè)分享.

隨后， 計(jì)算服務(wù)器將所有的Sum(Hq, j,Di, j)(1≤i≤l)， 發(fā)送給數(shù)據(jù)服務(wù)器.由于哈希碼Hq與Di之間和的重建是在數(shù)據(jù)服務(wù)器上執(zhí)行， 因此根據(jù)CRT秘密分享技術(shù)的特點(diǎn)， 任意第j個(gè)計(jì)算服務(wù)器無(wú)法從Sum(Hq, j,Di, j)中推測(cè)出原始Sum(Hq,Di).

算法2 相似合并輸入: Simhash碼和分享輸出: 合并后密文PDF1. For 每個(gè)Simhash碼的和分享2. 重建Simhash碼間的和3. 計(jì)算出漢明距離4. EndFor5. If 漢明距離小于預(yù)定值6. 合并并返回PDF7. EndIf

具體相似合并過(guò)程如算法2所示.

3 實(shí)驗(yàn)結(jié)果與分析

在實(shí)驗(yàn)中， 使用一臺(tái)8 GB 內(nèi)存、 Intel(R) Core(TM) i5-7500 CPU的一體機(jī)， 采用(3, 5)-CRT秘密分享技術(shù)， 即選取k=3,n=5， 對(duì)外包安全合并中四個(gè)不同算法： 合并請(qǐng)求、 模和計(jì)算、 數(shù)據(jù)庫(kù)Simhash碼加密、 相似合并進(jìn)行計(jì)算開(kāi)銷(xiāo)對(duì)比實(shí)驗(yàn)， 對(duì)應(yīng)的兩兩互素的集合是{29, 31, 37, 41, 43}， 伸縮因子s=47， 隨機(jī)噪聲ε<47， 代碼使用Matlab語(yǔ)言編寫(xiě). 理論上，k,n(k

通常在計(jì)算機(jī)視覺(jué)領(lǐng)域， 高維度的特征具有更優(yōu)異的辨別力， 往往能帶來(lái)更高的性能， 但也要付出更多的計(jì)算代價(jià). 如圖3(a)所示， 隨著Simhash碼維度增加， 合并請(qǐng)求就需要花費(fèi)更多的計(jì)算時(shí)間. 相對(duì)來(lái)說(shuō)， 合并請(qǐng)求算法的時(shí)間開(kāi)銷(xiāo)比較小， 比如維度為1 024時(shí)， 其計(jì)算時(shí)間僅為0.070 6 ms， 這主要是因?yàn)楹喜⒄?qǐng)求算法僅需加密一個(gè)Simhash查詢碼. 為了測(cè)試PDF文件數(shù)目對(duì)所提方案中模和計(jì)算/數(shù)據(jù)庫(kù)Simhash碼加密/相似合并算法計(jì)算開(kāi)銷(xiāo)的影響， 選取5個(gè)數(shù)量不同PDF文件數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)， 結(jié)果如圖3(b)～(d)所示. 在給定維度情況下， 這三個(gè)算法的計(jì)算開(kāi)銷(xiāo)與數(shù)據(jù)集大小成正比， 所含文件越多計(jì)算開(kāi)銷(xiāo)越大. 比如給定特征維度為64， 當(dāng)PDF文件數(shù)目為100和500時(shí)， 模和計(jì)算/數(shù)據(jù)庫(kù)Simhash碼加密算法所對(duì)應(yīng)的運(yùn)行時(shí)間分別為1.27/4.70 ms， 6.17/24.33 ms， 而相似合并算法對(duì)應(yīng)的時(shí)間開(kāi)銷(xiāo)分別為1.52、 7.82 s. 在同等條件下， 相似合并算法的開(kāi)銷(xiāo)最大， 易導(dǎo)致響應(yīng)延遲， 從而影響用戶的體驗(yàn). 相似合并算法較高計(jì)算開(kāi)銷(xiāo)除了CRT重建秘密算法自身的原因外， 在一定程度上與所采用的單線程且過(guò)程非優(yōu)化的編程語(yǔ)言有關(guān)， 但無(wú)論如何對(duì)于具有海量計(jì)算能力的云服務(wù)器來(lái)說(shuō)， 這個(gè)算法很容易在云端被高效執(zhí)行. 同時(shí)， 從圖3(b)～(d)中也發(fā)現(xiàn)在同等大小數(shù)據(jù)集下， 模和計(jì)算/數(shù)據(jù)庫(kù)Simhash碼加密/相似合并算法效率會(huì)隨著特征維度的增加而降低. 為了完善實(shí)驗(yàn)結(jié)果， 并進(jìn)一步測(cè)試外包安全合并中四個(gè)不同算法與PDF文本數(shù)量的關(guān)系， 在另外3個(gè)數(shù)據(jù)量更大的數(shù)據(jù)集(即數(shù)據(jù)量為4 000， 8 000， 10 000個(gè))上進(jìn)行測(cè)試， 實(shí)驗(yàn)結(jié)果(Simhash碼長(zhǎng)度設(shè)置128， 其他參數(shù)設(shè)置保持不變)如表1所示， 其結(jié)論與上述實(shí)驗(yàn)保持一致. 其中， 合并請(qǐng)求計(jì)算開(kāi)銷(xiāo)跟數(shù)據(jù)集大小無(wú)關(guān)， 故保持不變.

(a) 合并請(qǐng)求算法計(jì)算開(kāi)銷(xiāo)

(b) 模和計(jì)算算法計(jì)算開(kāi)銷(xiāo)

(c) 數(shù)據(jù)庫(kù)Simhash碼加密開(kāi)銷(xiāo)

表1 不同算法計(jì)算開(kāi)銷(xiāo)對(duì)比

為了展示計(jì)算服務(wù)器數(shù)量(對(duì)應(yīng)就是CRT秘密分享技術(shù)中n的值)對(duì)不同算法的影響， 本文進(jìn)行了相應(yīng)的對(duì)比實(shí)驗(yàn)， 其中伸縮因子s=80， Simhash碼維度為128， PDF文件數(shù)量設(shè)為100， 計(jì)算服務(wù)器數(shù)量分別為6， 8， 10臺(tái)， 實(shí)驗(yàn)結(jié)果如表2所示. 顯然， 當(dāng)n增加時(shí)， 所有算法的開(kāi)銷(xiāo)均隨之變大. 相對(duì)來(lái)說(shuō)， 合并請(qǐng)求算法開(kāi)銷(xiāo)低于Simhash碼加密和相似合并算法， 這主要因?yàn)槠渲恍栳槍?duì)一個(gè)PDF文件特征操作. 同時(shí)本研究也發(fā)現(xiàn)： 模乘逆的操作使得相似合并算法的開(kāi)銷(xiāo)遠(yuǎn)大于Simhash加密與模和計(jì)算算法， 而模和計(jì)算僅牽涉到加法運(yùn)算， 其開(kāi)銷(xiāo)低于擁有更多運(yùn)算的Simhash加密算法.

表2 不同計(jì)算服務(wù)器數(shù)量下不同算法計(jì)算開(kāi)銷(xiāo)對(duì)比

除了文件數(shù)量和計(jì)算服務(wù)器數(shù)量對(duì)本研究所提方案性能有影響外， Simhash加密中u·s+ε式子也會(huì)增加方案整體的計(jì)算開(kāi)銷(xiāo)， 是影響系統(tǒng)性能的關(guān)鍵因素. 究其原因是以上四個(gè)算法都是在其基礎(chǔ)上設(shè)計(jì)的， 但其噪聲ε的隨機(jī)性使得本研究所提方案安全性得以進(jìn)一步提高， 甚至相同的明文可產(chǎn)生不同的密文， 使得特征向量每個(gè)元素的密文更加隨機(jī)化.

為了驗(yàn)證文中提出方案在完成相似度判斷和PDF文件合并的同時(shí)， 保證用戶隱私不被泄露. 選取兩個(gè)PDF文件進(jìn)行實(shí)驗(yàn)展示. 圖4顯示在解密的情況下， PDF文件合并前后的效果. 表3表明： 在本地用戶端可以得到完整的明文PDF文本信息； 經(jīng)過(guò)加密處理后， 在沒(méi)有密鑰的情況下， 數(shù)據(jù)服務(wù)器是無(wú)法識(shí)別出其具體的內(nèi)容.

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

表3 提取的文本在各參與方的表現(xiàn)形式

4 結(jié)語(yǔ)

提出一種基于Simhash的相似PDF外包安全自動(dòng)合并方法. 該方案利用中國(guó)剩余定理來(lái)加密PDF文件的特征向量， 并構(gòu)建漢明距離安全外包計(jì)算機(jī)制， 從而保證云端服務(wù)器在不知明文內(nèi)容的情況下， 實(shí)現(xiàn)密文PDF文件的相似性計(jì)算和合并任務(wù). 此外， CRT秘密分享技術(shù)也確保了PDF特征的信息理論安全， 其無(wú)密鑰的特性使得方案天然可推廣到多用戶的場(chǎng)景. 未來(lái)的工作在于提高相似性準(zhǔn)確度和系統(tǒng)運(yùn)行效率， 并支持非PDF文件的外包合并.