[發明專利]一種隱私保護的圖數據交集計算方法

有效

• 申請號: 201711306369.5
• 申請日: 2017-12-11
• 公開（公告）號: CN108055118B
• 公開（公告）日: 2020-06-05
• 發明（設計）人: 周福才;徐紫楓;李宇溪;秦詩悅
• 申請（專利權）人: 東北大學
• 主分類號: H04L9/00
• 分類號: H04L9/00;G06F21/62;G06F21/60
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 陳玲玉;梅洪玉

本發明屬于圖數據交集計算領域，提出了一種隱私保護的圖數據交集計算方法。在兩方實體之間完成圖數據交集計算，并且在計算過程中保護雙方圖數據的隱私；協議中使用了Paillier加密系統，來實現密文上的同態加法和同態乘法；協議擁有計算高效和泄漏信息少等特點。本發明可以安全的將其密態圖結構外包到一個不被信任的云服務器中，同時又不失去對其進行查詢的能力。可以充分的使用云服務器提供的存儲服務，同時放心地將查詢操作交給服務器來執行，可以保證服務器在交互的過程中盡量無法得到有效信息。

技術領域

本發明屬于圖數據交集計算領域，具體涉及一種隱私保護的圖數據交集計算方法。

背景技術

圖結構數據和圖數據處理在近年來持續獲得越來越多的研究和關注。在最近幾年，很多應用領域開始將傳統數據轉換為圖結構形式進行存儲，并使用圖運算來幫助解決很多計算類問題，包括社交網絡、生物信息學、通信網絡和交通網絡等。例如，網頁數據可以很自然地被表示和存儲為圖結構數據，其中靜態網頁被表示為圖中的點，網頁之間的鏈接被表示為圖中的邊。之后通過使用多種不同的圖運算，可以幫助解決很多網頁數據的計算問題，包括網頁搜索、網頁數據挖掘、網頁爬取等等。

圖交集計算的目的是計算兩個圖之間相交的部分，即計算兩個圖之間共有的點和邊。圖交集計算作為圖運算中最基本的計算之一，是很多實際應用中不可缺少的一部分，例如圖結構數據的數據挖掘等。

隨著大數據時代的發展，數據的產生速度、規模和計算量不斷上升，個體對大規模圖數據的存儲和計算變成了一個挑戰性難題。例如，對于一個擁有上百萬點和邊的圖，個人計算機很難對其進行高效的存取和計算。因此越來越多的個人和企業選擇使用云存儲服務來存放海量的圖結構數據，并使用云計算服務來對圖數據進行運算。

云存儲和云計算為使用者提供了便利，并極大地幫助使用者節省了存儲資源和運算資源。然而云存儲和云計算的提供商往往為不可信實體，其擁有內部和外部兩方面的威脅。其中內部威脅指的是服務提供商的內部成員可以直接查看并獲取使用者的數據，并對數據擁有完全的控制權；外部威脅指的是服務提供商的服務器被外部人員進行有預謀或無意的攻擊，從而導致使用者的數據丟失或被竊取。

目前基于圖數據交集計算的相關研究在安全性和隱私保護方面存在很多問題，無法保證云計算中用戶的數據隱私。針對云計算和圖交集計算的特點，亟需一種可以抵抗內部和外部威脅的圖交集計算的方法和系統，它能夠在不可信的環境下保證計算的隱私性和機密性。

發明內容

本發明的目的在于提供一種隱私保護的圖數據交集計算方法，可以在兩方實體之間完成圖數據交集計算，并且在計算過程中保護雙方圖數據的隱私；協議中使用了Paillier加密系統，來實現密文上的同態加法和同態乘法；協議擁有計算高效和泄漏信息少等特點。

本發明的技術方案：

隱私保護的圖數據交集計算協議包括兩方實體：Alice和Bob。Alice是協議的請求發起者，其持有私有圖數據G_A。Bob是協議的請求應答者，其持有私有圖數據G_B。

Alice和Bob所持有的圖數據是圖論中的有向圖，并且圖中的每個點都擁有唯一的標識。在協議的過程中，Alice和Bob都希望保護他們所持有的圖數據的隱私。圖數據的隱私指的是任何關于圖的信息，包括圖中點的數量、邊的數量、點的標識等等。

在協議完成后，Alice獲得兩個圖之間的交集G_I，Bob獲得兩個圖之間點的交集V_I。其中兩個圖的交集G_I是由兩個圖中共同存在的點和邊組成的圖，兩個圖之間點的交集V_I是由兩個圖中共同存在的點組成的集合。

隱私保護的圖數據交集計算協議中，Alice和Bob持有的私有圖數據被表示為G＝(V,E)，其中G是圖數據，V是圖中點的集合，E是圖中邊的集合。