[發(fā)明專利]一種隱私保護(hù)的圖數(shù)據(jù)交集計(jì)算方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201711306369.5
• 申請(qǐng)日: 2017-12-11
• 公開（公告）號(hào): CN108055118B
• 公開（公告）日: 2020-06-05
• 發(fā)明（設(shè)計(jì)）人: 周福才;徐紫楓;李宇溪;秦詩(shī)悅
• 申請(qǐng)（專利權(quán)）人: 東北大學(xué)
• 主分類號(hào): H04L9/00
• 分類號(hào): H04L9/00;G06F21/62;G06F21/60
• 代理公司: 大連理工大學(xué)專利中心 21200
• 代理人: 陳玲玉;梅洪玉

1.一種隱私保護(hù)的圖數(shù)據(jù)交集計(jì)算方法，其特征在于，步驟如下：

步驟1，定義隱私保護(hù)的圖數(shù)據(jù)交集計(jì)算協(xié)議包括兩個(gè)參與者：Alice和Bob；Alice是協(xié)議的請(qǐng)求發(fā)起者，其持有私有圖數(shù)據(jù)G_A，私有圖數(shù)據(jù)G_A中點(diǎn)的數(shù)量為m；Bob是協(xié)議的請(qǐng)求應(yīng)答者，其持有私有圖數(shù)據(jù)G_B，私有圖數(shù)據(jù)G_B中點(diǎn)的數(shù)量為n；私有圖數(shù)據(jù)G_A和私有圖數(shù)據(jù)G_B是圖論中的有向圖；Alice生成Paillier加密系統(tǒng)的公鑰pk和私鑰sk，并將公鑰pk發(fā)送給Bob；

步驟2，Alice根據(jù)其持有的私有圖數(shù)據(jù)G_A中點(diǎn)的集合V_A生成多項(xiàng)式P(x)，P(x)的所有根為V_A中的所有元素；之后Alice使用Paillier加密系統(tǒng)從低次項(xiàng)到高次項(xiàng)加密P(x)的所有系數(shù)，并將所有密文發(fā)送給Bob；

步驟3，

3.1)Bob根據(jù)Paillier加密系統(tǒng)的同態(tài)性，將其持有的私有圖數(shù)據(jù)G_B中所有的點(diǎn)b_i作為P(x)的輸入；其中：b_i∈V_B，i＝1,2,…,n；

3.2)通過收到的密文計(jì)算P(x)的解，得到e_i＝P(b_i)；之后對(duì)所有的e_i，計(jì)算r_i：

其中：γ是隨機(jī)數(shù)，是Paillier同態(tài)乘法；是Paillier同態(tài)加法；

3.3)最后將所有的r_i發(fā)送給Alice；

步驟4，

4.1)Alice解密所有收到的r_i，并和其持有的私有圖數(shù)據(jù)G_A中點(diǎn)的集合V_A進(jìn)行對(duì)比；

若Dec(r_i)在V_A中存在相同的元素，即Dec(r_i)＝a_j，則a_j是Alice持有的私有圖數(shù)據(jù)G_A和Bob持有的私有圖數(shù)據(jù)G_B中共有的點(diǎn)；

4.2)在對(duì)比完所有的Dec(r_i)后，Alice得到了Alice持有的私有圖數(shù)據(jù)G_A和Bob持有的私有圖數(shù)據(jù)G_B中點(diǎn)的交集V_I

V_I＝V_A∩V_B

4.3)最后Alice將V_I發(fā)送給Bob；

步驟5，

5.1)Alice通過使用V_I和E_A計(jì)算新的鄰接矩陣E′_A；E′_A是E_A的一部分，E_A包含私有圖數(shù)據(jù)G_A中所有點(diǎn)之間的鄰接關(guān)系，而E′_A只包含V_I中的點(diǎn)之間的鄰接關(guān)系；V_I中點(diǎn)的個(gè)數(shù)為t，E′_A是一個(gè)t×t的方陣；

5.2)Alice使用Paillier加密系統(tǒng)加密E′_A中的所有元素，得到密文矩陣C_A，并將密文矩陣C_A發(fā)送給Bob；

步驟6，

6.1)Bob通過使用V_I和E_B計(jì)算新的鄰接矩陣E′_B；E′_B是E_B的一部分，E_B包含私有圖數(shù)據(jù)G_B中所有點(diǎn)之間的鄰接關(guān)系，而E′_B只包含V_I中的點(diǎn)之間的鄰接關(guān)系；V_I中點(diǎn)的個(gè)數(shù)為t，E′_B是一個(gè)t×t的方陣；6.2)之后將E′_B中的所有元素與密文矩陣C_A中相同位置的元素進(jìn)行Paillier同態(tài)乘法，即計(jì)算其中1≤i,j≤t，E′_B[i,j]表示矩陣E′_B中第i行第j列隊(duì)的值，C_A[i,j]表示矩陣C_A中第i行第j列隊(duì)的值，得到一個(gè)密文矩陣C_B；

6.3)最后將C_B發(fā)送給Alice；

步驟7，Alice使用Paillier的私鑰sk解密C_B，并得到Alice持有的私有圖數(shù)據(jù)G_A和Bob持有的私有圖數(shù)據(jù)G_B中邊的交集E_I；此時(shí)Alice同時(shí)得到了V_I和E_I，即Alice持有的私有圖數(shù)據(jù)G_A和Bob持有的私有圖數(shù)據(jù)G_B的交集G_I；

所述方法中：Enc()是Paillier加密算法；Dec()是Paillier解密算法；V_A是Alice持有的私有圖數(shù)據(jù)G_A中點(diǎn)的集合；V_B是Bob持有的私有圖數(shù)據(jù)G_B中點(diǎn)的集合；E_A是Alice持有的私有圖數(shù)據(jù)G_A中邊的集合；E_B是Bob持有的私有圖數(shù)據(jù)G_B中邊的集合。