[發明專利]基于雙云模型的云外包數據隱私保護頻繁項挖掘方法

有效

• 申請號: 202010540127.8
• 申請日: 2020-06-13
• 公開（公告）號: CN111698078B
• 公開（公告）日: 2022-04-19
• 發明（設計）人: 陳榮茂;王小峰;柳林;邢倩倩;王毅;陳錦榕
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: H04L9/00
• 分類號: H04L9/00;H04L9/08;H04L9/40;H04L67/10;G06F21/62;G06F16/90
• 代理公司: 湖南企企衛知識產權代理有限公司 43257
• 代理人: 任合明

1.一種基于雙云模型的云外包數據隱私保護頻繁項挖掘方法，針對如下定義的參數：BCP密碼算法的明文空間是Z_N，密文空間是加性秘密共享的明文空間和密文空間均為Z_P，且滿足P≤N，[x]_pk表示公鑰pk對明文x加密后的密文；對于某一個明文y∈Z_P，用y表示y的共享份，其中y^A和y^B分別表示屬于云服務平臺CSP和輔助計算的云ESP的共享份，N的比特長度為l，系統中一共有η個數據擁有者，數據擁有者上傳的數據集一共有m條事務數據，且每一條事務數據表示的布爾向量長度為n；用戶上傳的項分別可以表示為Item_k，其中k∈[1,n]，頻繁項挖掘中的最小支持度為min，l,η,m,n和min都是自然數；其特征在于，該方法主要包括如下步驟：

S1密鑰生成中心為數據擁有者生成BCP加密算法的公私鑰對pk_i/sk_i，i∈[1,η]，并將其分發給用戶；同時也為CSP生成公私鑰對pk_A/sk_A；此外還生成BCP密碼算法的主密鑰MK，并將MK分發給ESP；

S2每一個用戶收到公鑰pk_i后，數據擁有者利用公鑰pk_i加密待外包數據，并將密文傳輸至CSP；數據擁有者分別利用公鑰pk_i將每一條待外包數據表示成布爾向量其中d_j,k∈{0,1}，當d_j,k＝1時表示Item_k在當中；并把它們加密為待外包數據集的密文向量表示d_j,k用公鑰pk_i加密后對應的密文，其中i∈[1,η]，j∈[1,m]，k∈[1,n]；然后，每一個用戶都將發送給CSP，從而CSP得到加密后的外包數據集[D]；

S3 CSP通過和ESP聯合計算，將收到待外包數據集[D]轉換成加性秘密共享數據集D：即對于中的每一個CSP和ESP將其轉化為d_j,k，d_j,k表示d_j,k的加性秘密共享份，其中d_j,k^A表示d_j,k屬于CSP的加性秘密共享份，d_j,k^B表示d_j,k屬于ESP的加性秘密共享份；該轉換過程主要包括以下步驟：

S3.1對于CSP從Z_P中隨機選擇一個數a_j,k，并令d_j,k^A←a_j,k；然后利用pk_i將a_j,k加密為

S3.2 CSP計算并將結果標記為表示b_j,k用公鑰pk_i加密后對應的密文，然后將發送給ESP；

S3.3 ESP收到后，利用S1生成的BCP算法的主密鑰MK，將解密并將結果標記為d_j,k^B←b_j,k；

S3.4 CSP和ESP循環運行S3.1至S3.3，直到將所有的都轉化為d_j,k；CSP將轉化后的數據集d_j,k標記為其中D是一個m行n列的矩陣且這樣CSP和ESP就得到了加性秘密共享數據集D；

S4 CSP和ESP從共享的數據集D上挖掘出頻繁一項集，并生成候選頻繁二項集；具體步驟如下：

S4.1對于D的每一列，CSP和ESP分別計算和并將結果標記為s_k^A和s_k^B，其中k∈[1,n]；

S4.2 ESP利用CSP的公鑰pk_A將每一個s_k^B加密為并將其傳輸給CSP；

S4.3 CSP利用公鑰pk_A，將每一個s_k^A加密為CSP計算并將結果標記為

S4.4 CSP利用公鑰pk_A將頻繁項挖掘中的最小支持度min加密為然后CSP和ESP運行密文比較算法得到和的比較結果；假設待比較的兩個數和的比特長度均小于l/2，那么和密文比較算法的主要步驟如下所示：

S4.4.1 CSP從{0,1}中隨機挑選一個數，并將其標記為a_k，k∈[1,n]；如果a_k＝1，CSP計算否則，CSP計算并將結果標記為C_k；

S4.4.2 CSP隨機挑選一個小于2^l的數，并將其標記為r_k；接下來，CSP利用公鑰pk_A加密r_k，從而得到其密文然后計算并將計算結果標記為E_k；CSP將E_k發送給ESP；

S4.4.3 ESP收到E_k后，利用S1生成的BCP算法的主密鑰MK將其解密，并將結果標記為e_k；如果e_k≤N/2，則記b_k＝1，否則記b_k＝0；ESP將b_k發送給CSP；

S4.4.4如果a_k＝0，CSP令Cpm_k＝b_k；否則令Cmp_k＝1-b_k；最后輸出的Cmp_k就是比較結果；

S4.5令Item_k表示頻繁一項集，對于每一個Cmp_k,k∈[1,n]，如果Cmp_k＝1，則CSP將用戶上傳的項Item_k放入頻繁一項集中，即frequent_1_items∪Item_k，即認為Item_k是頻繁項；否則Item_k不是頻繁項；完成這一步驟后，CSP即可得到所有的頻繁一項集frequent_1_items；

S5 CSP和ESP從頻繁二項集候選集中挖掘出頻繁二項集，再從頻繁二項集生成頻繁三項集候選集并繼續挖掘，直到無法生成新的候選項集為止；CSP根據S4.5挖掘的頻繁一項集frequent_1_items生成頻繁二項集候選集，即candidate_2_items，然后從candidate_2_items中挖掘出頻繁二項集frequent_2_items；由于從項候選集挖掘到頻繁項集的方法步驟相同，本步驟僅描述從candidate_2_items挖掘出frequent_2_items的步驟，具體如下，假設頻繁二項集候選集一共有p個項候選集，且每一個都可以表示為α_t,k∈{0,1}，其中t∈[1,p]，k∈[1,n]：

S5.1對于每一個CSP和ESP計算和的內積，并將結果標記為ξ_t,j，其中且α_t,k^A＝α_t,k，α_t,k^B＝0，t∈[1,p]，j∈[1,m]，k∈[1,n]；其中和的內積運算主要包括以下步驟：

S5.1.1 CSP和ESP對每一個α_t,k和d_j,k運行安全乘法算法，并將結果標記為αd_j,k，其中αd_j,k^A表示屬于CSP，αd_j,k^B表示屬于ESP；

S5.1.2 CSP計算并將結果標記為ξ_t,j^A；ESP計算并將結果標記為ξ_t,j^B；

S5.2 ESP利用CSP的公鑰pk_A將每一個ξ_t,j^B，t∈[1,p]，j∈[1,m]，加密為并將其傳輸給CSP；

S5.3 CSP利用公鑰pk_A將每一個ξ_t,j^A加密為計算并將結果標記為

S5.4 CSP利用公鑰pk_A加密計算然后CSP和ESP運行密文比較算法，比較與的大小，并得到比較結果，記為Cmp2_t,j；

S5.5對于每一個t∈[1,p]，CSP計算并將結果標記為Supp2_t；

S5.6 CSP比較min與Supp2_t：如果Supp2_t＞min，則是頻繁二項集，CSP令否則不是頻繁二項集；

S6重復S5，最終CSP得到外包數據集的全部頻繁項。