雲端服務下以布隆過濾器為基礎之匿名搜尋效能研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：16

、訪客IP：18.223.32.230

姓名

張雅淇(Ya-Chi Chang) 查詢紙本館藏

畢業系所

資訊管理學系

論文名稱

雲端服務下以布隆過濾器為基礎之匿名搜尋效能研究
(Bloom Filter based Research on Anonymous Search Performance on Cloud Service)

相關論文

★ 應用數位版權管理機制於數位影音光碟內容保護之研究	★ 以應用程式虛擬化技術達成企業軟體版權管理之研究
★ 以IAX2為基礎之網頁電話架構設計	★ 應用機器學習技術協助警察偵辦詐騙案件之研究
★ 擴充防止詐欺及保護隱私功能之帳戶式票務系統研究-以大眾運輸為例	★ 網際網路半結構化資料之蒐集與整合研究
★ 電子商務環境下網路購物幫手之研究	★ 網路安全縱深防護機制之研究
★ 國家寬頻實驗網路上資源預先保留與資源衝突之研究	★ 以樹狀關聯式架構偵測電子郵件病毒之研究
★ 考量地區差異性之隨選視訊系統影片配置研究	★ 不信任區域網路中數位證據保留之研究
★ 入侵偵測系統事件說明暨自動增加偵測規則之整合性輔助系統研發	★ 利用程序追蹤方法關聯分散式入侵偵測系統之入侵警示研究
★ 一種網頁資訊擷取程式之自動化產生技術研發	★ 應用XML/XACML於工作流程管理系統之授權管制研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

現今由於雲端服務越來越普及，不僅僅是雲端服務供應商，其他產業的業者也開始蒐集使用者的資訊上傳至雲端進行儲存和分析，以期提供更好的使用者體驗服務，但蒐集大量資料的同時，要如何去保障使用者的隱私是一個相當重要的議題。
有研究提出以匿名方式進行使用者資訊保護，基於布隆過濾器來保障雲端環境下的使用者資訊，並且在匿名的同時還能夠提供查詢服務。但此機制有資料容納數量上的限制，且當資料負載量提高時，插入和搜尋資料的時間成本也會跟著提高，造成效能下降。
因此所以本研究提出Decay-Cuckoo Filter，在布穀鳥過濾器的雜湊表上做了一些改良，在原有的Bucket之後加上第二組Associate Bucket，用來儲存衰減係數(Decay Value)，一開始插入元素時，該元素的衰減係數為最大值，而此係數會隨著時間的經過、插入元素數量或者查詢元素素量達設定值後執行「衰減」，當某元素衰減係數衰減至最小值“0”，該元素將從資料表中被刪除，釋放空間。且本研究實驗證明，使用Decay Function方法其元素插入時間效能提升了1.4倍，元素的查詢時間效能提升了2倍。

摘要(英)

Nowadays, due to the increasing popularity of cloud services, not only cloud service providers, but also industry players in other industries have begun to collect user information and upload it to the cloud for storage and analysis, in order to provide better user experience services, but collect a large amount of data. At the same time, how to protect the privacy of users is a very important issue.
Some studies have proposed to protect user information in an anonymous manner. Based on the Bloom filter, user information in the cloud environment is guaranteed, and the query service can be provided while being anonymous. However, this mechanism has a limitation on the number of data storage, and as the data load increases, the time cost of inserting and searching for data will also increase, resulting in a decrease in performance.
Therefore, this study proposes a Decay Value as the usage weight value of each data, and a set of Decay Function to let the attenuation value decay with the custom conditions, when the attenuation value is reduced to At the minimum value, the data is removed from the data sheet to release the location, extending the life of the data sheet and improving its performance. And this research experiment proves that using the Decay Function method, the element insertion time is increased by 1.4 times, and the element query time is increased by 2 times.

關鍵字(中)

★ 隱私保護
★ 匿名搜尋
★ 布隆過濾器
★ 布穀鳥過濾器
★ 衰減函式

關鍵字(英)

★ Privacy-Preserving
★ Anonymous Search
★ Bloom Filter
★ Cuckoo Filter
★ Decay Function

論文目次

目錄 i
圖目錄 iii
表目錄 xii
第一章緒論 1
1-1 研究背景 1
1-2 研究動機與目的 3
1-3 研究方法與主要成果 6
1-4 章節架構 7
第二章相關研究 8
2-1 現有雲端加密方法 8
2-2 雲端搜尋運作架構 10
2-3 Bloom Filter（布隆過濾器） 10
2-2.1 Standard Bloom Filter 運作原理 10
2-2.2 Bloom Filter誤判率最佳解 12
2-2.3 Bloom Filter 應用於SNS 14
2-4 Counting Bloom Filter 16
2-5 Variable-Increment Counting Bloom Filter （VICBF） 17
2-6 Cuckoo Filter 20
2-6.1 Standard Cuckoo Hashing 20
2-6.2 Partial-key Cuckoo Hashing 21
2-6.3資料表大小配置 22
2-7 小結 23
第三章研究方法 24
3-1 Time-Dependent Bloom Filter 24
3-2 LRU (Least recently used) 26
3-3 Decay-Cuckoo Filter機制設計 27
3-4 Decay-Cuckoo Filter運作流程 29
第四章實驗與討論 32
4-1 實驗環境與基本參數配置 32
4-2 Decay-Cuckoo Filter與Normal-Cuckoo Filter效能比較 33
4-3 Decay Function執行次數與效能評估 34
4-3.1 Decay Function執行次數與效能評估-刪除元素數量 34
4-3.2 Decay Function執行次數與效能評估-碰撞次數 35
4-4 Decay Function執行條件與效能評估 36
4-4.1 Decay Function執行條件與效能評估-刪除元素數量 37
4-4.2 Decay Function執行條件與效能評估-碰撞次數 38
4-5 時間成本評估 38
4-5.1 時間成本評估-插入與查詢時間成本 39
4-5.2 時間成本評估-Decay Function執行時間成本 40
4-6 討論 41
第五章結論與未來研究 43
5-1 研究結論與貢獻 43
5-2 研究限制 44
5-3 未來研究 44
參考文獻 46

參考文獻

[參考網站]
[1] Bloom Filters the math Retrieved (Accessed：20-Jun-2018) From http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html (Accessed：20-Jun-2017)
[2] EUGDPR .org “Home Page of EU GDPR” (Accessed：20-Jun-2018) From https://www.eugdpr.org
[3] The Next Web(2017). (Accessed：20-Jun-2018) From “Android malware spreads like wildfire: 350 new malicious APPs every hour” from https://tnw.to/2pBScst.
[4] TrendMicro(2016). (Accessed：20-Jun-2018) From “Information on Reported Vulnerabilities in Trend Micro Password Manager” form https://blog.trendmicro.com/information-on-reported-vulnerabilities-in-trend-micro-password-manager/
[5] We are social(2017). (Accessed：20-Jun-2018) From "DIGITAL IN 2017: GLOBAL OVERVIEW"from https://wearesocial.com/special-reports/digital-in-2017-global-overview.
[6] 經濟部標準檢驗局.“個人資料去識別化適用標準” (Accessed：20-Jun-2018) Fromhttps://www.bsmi.gov.tw/wSite/public/Data/f1447142556627.pdf
[中文文獻]
[7] 張瑋倫.“基於Bloom Filter之雲端環境下使用者匿名機制查詢研究.”中央大學資訊管理學系所碩士論文 (2017)
[8] 曹宗恆.“混合式硬碟緩衝快取區管理機制.” 交通大學資訊管理學系所碩士論文 (2006)
[英文文獻]
[9] Abdelhameed, S. A., Moussa, S. M., & Khalifa, M. E. (2017, December). Enhanced additive noise approach for privacy-preserving tabular data publishing. In Intelligent Computing and Information Systems (ICICIS), 2017 Eighth International Conference on (pp. 284-291). IEEE.
[10] Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422-426.
[11] Bao, S., Hathal, W., Cruickshank, H., Sun, Z., Asuquo, P., & Lei, A. (2017). A lightweight authentication and privacy-preserving scheme for VANETs using TESLA and Bloom Filters. ICT Express.
[12] Charu, A., & Philip, S. Y. (2008). Privacy-preserving data mining: Models and algorithms.
[13] Coffman, E. G., & Denning, P. J. (1973). Operating systems theory (Vol. 973). Englewood Cliffs, NJ: Prentice-Hall.
[14] Damopoulos, D., Kambourakis, G., & Portokalidis, G. (2014, April). The best of both worlds: a framework for the synergistic operation of host and cloud anomaly-based IDS for smartphones. In Proceedings of the Seventh European Workshop on System Security (p. 6). ACM.
[15] Domingo-Ferrer, J., & Torra, V. (2005). Ordinal, continuous and heterogeneous k-anonymity through microaggregation. Data Mining and Knowledge Discovery, 11(2), 195-212.
[16] Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D. (2014, December). Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies (pp. 75-88). ACM.
[17] Fan, L., Cao, P., Almeida, J., & Broder, A. Z. (2000). Summary cache: a scalable wide-area web cache sharing protocol. IEEE/ACM transactions on networking, 8(3), 281-293.
[18] Fountoulakis, N., Khosla, M., & Panagiotou, K. (2016). The multiple-orientability thresholds for random hypergraphs. Combinatorics, Probability and Computing, 25(6), 870-908.
[19] Kuroiwa, K., & Uda, R. (2012, February). A low cost privacy protection method for SNS by using bloom filter. In Proceedings of the 6th International Conference on Ubiquitous Information Management and Communication (p. 7). ACM.
[20] Machanavajjhala, A., Gehrke, J., Kifer, D., & Venkitasubramaniam, M. (2006, April). ell-Diversity: Privacy Beyondkappa-Anonymity. In null (p. 24). IEEE.
[21] Pagh, R., & Rodler, F. F. (2004). Cuckoo hashing. Journal of Algorithms, 51(2), 122-144.
[22] Pan, Y., Zhu, X. L., & Chen, T. G. (2012). Research on Privacy Preserving on K-anonymity. Journal of Software, 7(7), 1649-1656.
[23] Rashidi, B., Fung, C., & Vu, T. (2014, September). Recdroid: A resource access permission control portal and recommendation service for smartphone users. In Proceedings of the ACM MobiCom workshop on Security and privacy in mobile environments (pp. 13-18). ACM.
[24] Rottenstreich, O., Kanizo, Y., & Keslassy, I. (2014). The variable-increment counting Bloom filter. IEEE/ACM Transactions on Networking (TON), 22(4), 1092-1105.
[25] Shen, N., Yang, J., Yuan, K., Fu, C., & Jia, C. (2016). An efficient and privacy-preserving location sharing mechanism. Computer Standards & Interfaces, 44, 102-109.
[26] Smith, D. (2017). Secure pseudonymisation for privacy-preserving probabilistic record linkage. Journal of Information Security and Applications, 34, 271-279.
[27] Truong, H. T. T., Lagerspetz, E., Nurmi, P., Oliner, A. J., Tarkoma, S., Asokan, N., & Bhattacharya, S. (2014, April). The company you keep: Mobile malware infection rates and inexpensive risk indicators. In Proceedings of the 23rd international conference on World wide web (pp. 39-50). ACM.
[28] Vatsalan, D., & Christen, P. (2016). Multi-Party Privacy-Preserving Record Linkage using Bloom Filters. arXiv preprint arXiv:1612.08835.
[29] Vatsalan, D., & Christen, P. (2016). Privacy-preserving matching of similar patients. Journal of biomedical informatics, 59, 285-298.
[30] Wang, C. Y., Yang, W. P., Tseng, J. C., & Hsu, M. (1990). Random filter and its analysis. International journal of computer mathematics, 33(3-4), 181-194.
[31] Xie, K., Wang, X., Li, W., Zheng, Z., Xie, G., & Wen, J. (2016, June). Bloom-filter-based profile matching for proximity-based mobile social networking. In Sensing, Communication, and Networking (SECON), 2016 13th Annual IEEE International Conference on (pp. 1-9). IEEE.

指導教授

陳奕明(Yi-Ming Chen)

審核日期

2018-7-31

推文