雲端環境中利用k-isomorphism保護圖形結構隱私的技術之研究

The Study of Privacy Preserving Graph Structure in Cloud by Using K-Isomorphism

吳政軒(Cheng-Hsuan Wu)

指導教授 ： 黃仁俊

淡江大學/工學院/資訊工程學系碩士班/碩士(2014年)

https://doi.org/10.6846/TKU.2014.00243

摘要

日益成長的雲端技術使得雲端應用愈趨成熟，圖形是目前許多資訊處理與應用極為重要並倚賴的資料結構，因此使用者與企業在運用雲端之同時極有可能須將圖形的結構資料寄存至雲端，除善用其儲存系統儲存大量圖形資料，並借重其計算能力做有效率的處理，但圖形內含有許多重要且敏感的資訊，因此在上傳圖形結構前必須轉換成能夠隱藏資訊的外儲圖(outsource graph)以確保使用者的隱私。本論文提出方法將圖形轉換成k-isomorphism圖，該演算法酌量加入虛擬假節點(dummy vertex)與虛擬假邊(dummy edge)以及多個不同面向的策略挑選出k個互相同構的子圖，藉以將原始圖轉換成外儲圖；外儲圖即為寄存至雲端的實際圖形；雲端供應商雖可在此外儲圖上協助使用者進行各項運算與應用，但卻與第三者一樣無法了解或還原使用者的原始圖，達到保護圖形隱私之目的，本論文方法滿足k-security安全性，亦可以有效抵擋neighborhood attack、node identifier attack、structural attack與reconstruction attack。

關鍵字

圖形 ； 雲端計算 ； 隱私保護 ； k-isomorphism

並列摘要

The growing popularity of cloud technology makes the application of cloud become maturer. When data structure of graph becomes more important for processing data and application, user and companies always store structure of graph in cloud. They use data structure of graph by cloud’s large storage and efficient computation in cloud. But graphs have many important and sensitive information, those must transform to outsource graph for anonymity and ensure user’s privacy. This thesis designs an algorithm to add dummy vertices and dummy edges in the right time, and use some different strategies to select k subgraphs which are isomorphic to each other. The proposed algorithm transforms origin graphs to k-isomorphism graphs which are outsource graphs. Users store those outsource graphs in cloud. The suppliers of cloud provide some service to the user based on those outsource graphs, but the suppliers can’t know the connection of any two nodes in users’ original graphs. The graphs’ privacy is protected. The proposed algorithm satisfy k-security, and also resist neighborhood attack, node identifier attack, structural attack and reconstruction attack.

並列關鍵字

Graph ； Cloud Computing ； Privacy Preserving ； k-isomorphism

參考文獻

[1] J. Gao, J. Yu, R. Jin, J. Zhou, T. Wang, and D. Yang, Neighborhood privacy protected shortest distance computing in cloud, in Proc. of ACM COMAD, 2011.

[2] B. Zhou and J. Pei. Preserving privacy in social networks against neighborhood attacks. In ICDE, pp. 506–515, 2008.

[3] K. Liu and E. Terzi. Towards identity anonymization on graphs. In SIGMOD, 2008.

[4] L. Zou, L. Chen, and M. T. Ozsu. K-automorphism: A general framework for privacy preserving network publication. In VLDB, 2009.

[5] J. Cheng, A. W.-C. Fu, and J. Liu. K-isomorphism: privacy preserving network publication against structural attacks. In SIGMOD, pp. 459–470, 2010.