面向隱私保護的相似PDF文件外包自動合并方法

周勇， 翁錕源， 程航， 嚴娜招， 黃芹健

(福州大學數學與統計學院， 福建 福州 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文件的外包合并.