淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


系統識別號 U0002-0909201423264300
中文論文名稱 雲端環境中利用k-isomorphism保護圖形結構隱私的技術之研究
英文論文名稱 The Study of Privacy Preserving Graph Structure in Cloud by Using K-Isomorphism
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 102
學期 2
出版年 103
研究生中文姓名 吳政軒
研究生英文姓名 Cheng-Hsuan Wu
學號 601411209
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2014-06-17
論文頁數 54頁
口試委員 指導教授-黃仁俊
委員-楊中皇
委員-黃心嘉
委員-黃仁俊
中文關鍵字 圖形  雲端計算  隱私保護  k-isomorphism 
英文關鍵字 Graph  Cloud Computing  Privacy Preserving  k-isomorphism 
學科別分類 學科別應用科學資訊工程
中文摘要 日益成長的雲端技術使得雲端應用愈趨成熟,圖形是目前許多資訊處理與應用極為重要並倚賴的資料結構,因此使用者與企業在運用雲端之同時極有可能須將圖形的結構資料寄存至雲端,除善用其儲存系統儲存大量圖形資料,並借重其計算能力做有效率的處理,但圖形內含有許多重要且敏感的資訊,因此在上傳圖形結構前必須轉換成能夠隱藏資訊的外儲圖(outsource graph)以確保使用者的隱私。本論文提出方法將圖形轉換成k-isomorphism圖,該演算法酌量加入虛擬假節點(dummy vertex)與虛擬假邊(dummy edge)以及多個不同面向的策略挑選出k個互相同構的子圖,藉以將原始圖轉換成外儲圖;外儲圖即為寄存至雲端的實際圖形;雲端供應商雖可在此外儲圖上協助使用者進行各項運算與應用,但卻與第三者一樣無法了解或還原使用者的原始圖,達到保護圖形隱私之目的,本論文方法滿足k-security安全性,亦可以有效抵擋neighborhood attack、node identifier attack、structural attack與reconstruction attack。
英文摘要 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.
論文目次 目錄
第一章 前言 1
第二章 相關研究 4
2.1 相關技術與安全性定義 4
2.2 Cheng等學者方法簡介 6
2.2.1 Frequency Based Graph Synthesis演算法 9
2.2.2 Anonymize-PAG 演算法 10
2.2.3 i-Graph Formation 演算法 11
2.3 分析與討論Cheng等學者之方法 13
第三章 論文方法 15
3.1 本論文概要 16
3.2 演算法D:圖形的分析與匿名 19
3.3 演算法E:轉換處理子圖 23
3.4 演算法F:i-graph的構成 26
3.5 演算法G:i-graph的構成 28
第四章 討論與分析 30
4.1 Neighborhood Attack 30
4.2 Node Identifier Attack 31
4.3 Structural Attack 31
4.4 Reconstruction Attack 31
4.5 功能比較 32
第五章 結論與未來研究方向 33
參考文獻 34
Appendix 35

圖目錄
圖2-1(a):給定之原始圖G 6
圖2-1(b):由圖2-1(a)轉換後的Gk 6
圖2-2(a):原始圖G 8
圖2-2(b):特定之子圖g 8
圖2-2(c):圖G存在的Embedding 8
圖2-2(d):圖形G只存在的VDEmbed 8
圖3-1:EM表格對應之範例原始圖 17
圖3-2:EM表格對應之PGraph 17
圖3-3:本論文方法演算法之主體架構圖 18
圖4-1:neighborhood attack範例圖 30

表目錄
表2-1:符號定義 4
表2-2:VM表格範例 8
表3-1:EM表格範例 17
表3-2:CNT表格範例 17
參考文獻 [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.
[6] M. Hay, G. Miklau, D. Jensen, D. F. Towsley and P. Weis. Resisting structural re-identification in anonymized social networks. PVLDB 1(1), pp.102–114, 2008.
[7] M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava. Anonymizing social networks. Technical report No. 07-19, Computer Science Department, University of Massachusetts Amherst, 2007.
[8] A. Campan and T. M. Truta. A clustering approach for data and structural anonymity in social networks. In PinKDD, 2008.
[9] E. Zheleva and L. Getoor. Preserving the privacy of sensitive relationships in graph data. In PinKDD, pp. 153–171, 2007.
[10] X. Ying and X. Wu. Randomizing social networks: a spectrum preserving approach. In SDM, pp. 739–750, 2008.
[11] J. Gao, J. X. Yu, R. Jin, J. Zhou, T. Wang, D. Yang. Outsourcing shortest distance computing with privacy protection. In VLDB Journal, 2013.
[12] P. Samarati. Protecting respondents’ identities in microdata release. IEEE Transactions on Knowledge and Data Engineering (TKDE) 13(6), pp. 1010–1027, 2001.
[13] P. Samarati. Protecting respondents’ identities in microdata release. IEEE Transactions on Knowledge and Data Engineering (TKDE) 13(6), 1010–1027, 2001.
[14] L. Sweeney. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10(5), pp. 557–570, 2002.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2018-09-11公開。
  • 同意授權瀏覽/列印電子全文服務,於2018-09-11起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信