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

有效

• 申請?zhí)枺?/td>: 201710472920.7
• 申請日: 2017-06-21
• 公開（公告）號: CN109101360B
• 公開（公告）日: 2020-11-20
• 發(fā)明（設(shè)計）人: 楊雅輝;張勝軍;吳中海
• 申請（專利權(quán)）人: 北京大學
• 主分類號: G06F11/10
• 分類號: G06F11/10;G06F11/14;G06F3/06
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理有限公司 11200
• 代理人: 司立彬

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

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

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

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

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

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

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

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

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

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

5.如權(quán)利要求1所述的方法，其特征在于，對被破壞的文件塊進行恢復的方法為：設(shè)損壞的文件塊為(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是糾刪編碼的冗余塊數(shù)目，j≠i,當0≤i≤m-h時,h≠m、…、2m-h；當m≤i≤2m-h時,h≠0、…、m-h；然后水平方向上利用數(shù)據(jù)塊p_k和x_j采用糾刪編碼進行一次修復得到修復后的x_i，其中j≠i，交叉方向上利用數(shù)據(jù)塊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.如權(quán)利要求1所述的方法，其特征在于，所述布隆過濾器為計數(shù)型的布隆過濾器。

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