[發明專利]一種基于布隆過濾器和交叉編碼的數據完整性保護方法

有效

• 申請號: 201710472920.7
• 申請日: 2017-06-21
• 公開（公告）號: CN109101360B
• 公開（公告）日: 2020-11-20
• 發明（設計）人: 楊雅輝;張勝軍;吳中海
• 申請（專利權）人: 北京大學
• 主分類號: G06F11/10
• 分類號: G06F11/10;G06F11/14;G06F3/06
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 司立彬

1.一種基于布隆過濾器和交叉編碼的數據完整性保護方法，其步驟為：

1)用戶將文件傳送給可信第三方服務器TPA；

2)TPA對該文件進行分塊并進行糾刪編碼得到分塊的冗余校驗碼；然后記錄該文件的分塊信息，并利用文件塊和冗余校驗碼生成該文件的布隆過濾器；其中TPA對該文件進行分塊并進行糾刪編碼的方法為：首先將該文件劃分為n個文件塊b1、b2、...、bn；然后將每k個文件塊劃分為一組，將該組內k個文件塊劃分為沿兩個水平方向和兩個交叉方向排列的四個區域，構成一交叉編碼組，其中，每一區域包括m個文件塊；對每一交叉編碼組內水平和交叉方向的文件塊進行糾刪編碼，生成每個區域的冗余校驗碼；

3)TPA將該文件分塊及其冗余校驗碼上傳到云端；

4)當該用戶通過TPA向云端發起挑戰，即對該文件進行完整性檢測時，TPA查找該文件對應的文件塊，然后將挑戰內容發送至云端；

5)云端利用TPA發送過來的挑戰內容計算該文件的文件塊所對應的簽名值并返回給TPA；

6)TPA驗證該文件的布隆過濾器是否滿足各所述簽名值的查詢，如果不滿足簽名值i的查詢，則判定該簽名值i對應的文件塊被破壞；TPA將驗證結果返回給用戶。

2.如權利要求1所述的方法，其特征在于，采用動態存儲表記錄該文件的分塊信息，所述動態存儲表包括動態數據組表和動態數據塊表；其中，所述動態數據組表用來管理所述交叉編碼組，每一動態數據組表與一動態數據塊表對應，所述動態數據塊表中記錄對應動態數據組表內的文件塊和冗余校驗碼的基本信息。

3.如權利要求2所述的方法，其特征在于，所述動態數據塊表中記錄的信息包括文件塊的邏輯位置、大小、是否需要存儲在云端、指向物理地址的下一個位置和指向物理地址的前一個位置。

4.如權利要求2所述的方法，其特征在于，TPA通過動態存儲表查找該文件對應的文件塊。

5.如權利要求1所述的方法，其特征在于，對被破壞的文件塊進行恢復的方法為：設損壞的文件塊為(x_i,y_i)，其中x_i,y_i為交叉編碼組中兩個不同水平方向上的文件塊；對文件塊(x_i,y_i)進行修復的方法為：首先從文件塊(x_i,y_i)所在交叉編碼組中提取3m個文件塊，即(p_k,p_k+4)和(x_j,y_h)；其中，0≤k≤r-h，r是糾刪編碼的冗余塊數目，j≠i,當0≤i≤m-h時,h≠m、…、2m-h；當m≤i≤2m-h時,h≠0、…、m-h；然后水平方向上利用數據塊p_k和x_j采用糾刪編碼進行一次修復得到修復后的x_i，其中j≠i，交叉方向上利用數據塊p_k+4和(x_j,y_h)采用糾刪編碼進行一次修復，其中，當0≤i≤m-h時,m≤j≤2m-h,0≤h≤m-h,h≠i，當m≤i≤2m-1時,0≤j≤m-1,m≤h≤2m-h,h≠i。

6.如權利要求1所述的方法，其特征在于，所述布隆過濾器為計數型的布隆過濾器。

7.如權利要求1所述的方法，其特征在于，所述挑戰內容包括該文件的文件塊信息及計算文件塊簽名值的程序。