(3.230.76.48) 您好!臺灣時間:2021/04/13 15:35
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:張豐麒
研究生(外文):Chang, Feng-Chi
論文名稱:用於多媒體分析與檢索的隱私保護二元圖配對架構
論文名稱(外文):A Privacy-Preserving Bipartite Graph Matching Framework for Multimedia Analysis and Retrieval
指導教授:朱威達
指導教授(外文):Chu, Wei-Ta
口試委員:陳祝嵩許秋婷張傳育朱威達
口試委員(外文):Chen, Chu-SongHsu, Chiou-TingChang, Chaun-YuChu, Wei-Ta
口試日期:2013-07-02
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:48
中文關鍵詞:二元圖配對隱私保護Paillier加密法DGK加密法匈牙利演算法亂碼電路
外文關鍵詞:Bipartite graph matchingPrivacy preservingThe Paillier cryptosystemThe DGK cryptosystemThe Hungarian algorithmThe garbled circuit
相關次數:
  • 被引用被引用:0
  • 點閱點閱:266
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:27
  • 收藏至我的研究室書目清單書目收藏:0
雲端運算技術的興起,提供無限量的運算能力與儲存空間的環境,為多媒體分析與檢索的研究帶來新契機。然而使用者的隱私,例如搜尋的意圖,可能會洩漏給伺服器,也有可能會被外來的公司或個人惡意利用。本論文提出一個隱私保護的多媒體分析架構,基於被廣泛利用的二元圖配對(bipartite graph matching),讓多媒體分析與檢索的技術能夠在加密域(encryption domain)下運作。本論文重點在於讓伺服器不知道使用者想要搜尋什麼,並希望能完善地利用伺服器的強大運算能力來幫忙使用者搜尋。為了完成二元圖的建構與配對,我們整合同態加密法(homomorphic encryption)與溝通機制,來處理在加密域下的權重計算與匈牙利演算法(Hungarian algorithm)。除此之外,我們利用亂碼電路(garbled circuit)讓二元圖配對演算法的運算更有效率。我們基於隱私保護的架構實作影片標註(video tag suggestion)與複製影片偵測(video copy detection)兩個應用,以及利用實驗結果證明在加密域下與在明文域下的效能並駕齊驅。
從不同的觀點來看,我們提出一個利用標籤分群的階層式架構,縮減挑選標籤的數量來降低運算時間。我們也提出新的互動式隱私保護機制,讓伺服器利用使用者回饋的資訊來改善系統效能。由於二元圖配對的普遍性,我們提出的架構能被認可並可利用於各種能保護隱私的多媒體檢索應用上。

The emergence of cloud computing provides unlimited computation/storage environment for users, and offers new opportunities for multimedia analysis and retrieval research. However, privacy of users, e.g., search intention, could be leaked to the server and may be maliciously utilized by companies or individuals with animus. This thesis presents a privacy-preserving multimedia analysis framework based on a widely-adopted structure, i.e., bipartite graph, so that multimedia analysis and retrieval in the encryption domain is enabled. This thesis aims to keep the retrieval server unaware of what the user wants to retrieve, and at the same time take full advantage of the server’s computation power. To accomplish bipartite graph construction and matching, homomorphic encryption systems and communication protocols in the encryption domain are integrated to carry out encrypted edge weight calculation and the Hungarian algorithm. Besides, the garbled circuit is employed to efficiently find minimum in the graph matching algorithm. Two applications of video tag suggestion and video copy detection are developed based on the privacy-preserving framework, and the evaluation results demonstrate that performance obtained in the encryption domain is comparable with that obtained in the plain text domain.
From an alternative perspective, we present a hierarchical framework with tag clustering to reduce computation due to the shrunk candidate space. The newly proposed interactive privacy-preserving scheme enables the server to adopt user feedback to improve performance. Thanks to the generality of bipartite graph matching, the proposed framework is believed to be employed in various privacy-preserving retrieval, annotation, and detection tasks.

Chapter 1 INTRODUCTION 1
1.1 Motivation 1
1.2 Related Works 4
1.2.1 Privacy-Preserving Multimedia Retrieval 4
1.2.2 Bipartite Graph Matching for Multimedia Retrieval 5
1.3 Contributions 6
1.4 Thesis Organization 7
Chapter 2 Cryptographic Tools 8
2.1 Paillier Cryptosystem 8
2.2 DGK Cryptosystem 9
2.3 Garbled Circuits 10
2.4 Oblivious Transfer 13
2.5 Summary 13
Chapter 3 Privacy-Preserving Bipartite Graph Construction and Matching 14
3.1 Basics of Bipartite Graph Matching 14
3.1.1 Formulation of Bipartite Graph Matching 14
3.1.2 The Hungarian Algorithm 15
3.2 Graph Construction 16
3.3 Minimum-Cost Bipartite Graph Matching 19
3.3.1 The Comparison Protocol 20
3.3.2 Checking Zero 22
3.3.3 Garbled Circuit for Minimum Search 23
3.4 Summary 25
Chapter 4 Applications 27
4.1 Video Tag Suggestion and Localization 27
4.2 Video Copy Detection 29
4.3 Summary 31
Chapter 5 Evaluation 32
5.1 Privacy-Preserving Tag Suggestion 32
5.2 Privacy-Preserving Video Copy Detection 35
5.3 Discussions 36
5.3.1 Improvement with Tag Clustering 36
5.3.2 A User Feedback Framework 39
5.4 Summary 40
Chapter 6 Conclusion and Future Works 42
6.1 Conclusion 42
6.2 Future Works 43
REFERENCES 44
APPENDIX 48
[1]R. Agrawal and R. Srikant. Privacy-preserving data mining. Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 439-450, 2000.
[2]A. Swaminathan, Y. Mao, G.-M. Su, H. Gou, A. Varna, S. He, M. Wu, and D. Oard. Confidentiality-preserving rank-ordered search. Proceedings of ACM Workshop on Storage Security and Survivability, pp. 7-12, 2007
[3]R. Diestel. Graph Theory. Heidelberg, Springer, 2005.
[4]P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. Proceedings of the International Conference on Theory and Application of Cryptographic Techniques, pp. 223-238, 1999.
[5]I. Damgard and M. Jurik. A generalization, a simplification and some applications of Paillier’s probabilistic public-key system. Technical Report, Department of Computer Science, University of Aarhus, 2000.
[6]I. Damgard, M. Geisler, and M. Kroigaard. Efficient and secure comparison for online auctions. Proceedings of the Australasian Conference on Information Security and Privacy, pp. 416-430, 2007.
[7]I. Damgard, M. Geisler, and M. Kroigaard. A correction to efficient and secure comparison for online auctions. International Journal of Applied Cryptography, vol. 1, no. 4, pp. 323-324, 2009.
[8]J. Shashank, P. Kowshik, K. Srinathan, and C. Jawahar. Private content based image retrieval. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2008.
[9]W. Lu, A. Swaminathan, A.L. Varna, and M. Wu. Enabling search over encrypted multimedia databases. Proceedings of SPIE Conference on Media Forensics and Security, 2009.
[10]C.-Y. Hsu, C.-S. Lu, and S.-C. Pei. Image feature extraction in encrypted domain with privacy-preserving SIFT. IEEE Transactions on Image Processing, vol. 21, no. 11, pp. 4593-4607, 2012.
[11]Z. Erkin, M. Franz, and J. Guajardo. Privacy-preserving face recognition. Proceedings of International Symposium on Privacy Enhancing Technologies, pp. 235-253, 2009.
[12]A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. Efficient privacy-preserving face recognition. Proceedings of International Conference on Information Security and Cryptology, pp. 229-244, 2009.
[13]Z.K.G. do Patrocinio, S.J.F. Guimaraes, and H.B. de Paula. Bipartite graph matching for video clip localization. Proceedings of Brazilian Symposium on Computer Graphics and Image Processing, pp. 129-138, 2007.
[14]S.J.F. Guimaraes, Z.K.G. do Patrocinio, K.J.F. Souza, and H.B. de Paula. Gradual transition detection based on bipartite graph matching. Proceedings of IEEE International Workshop on Multimedia Signal Processing, 2009.
[15]H. Xu, L. Liu, L.-F. Sun, and S.-Q. Yang. Fast and robust detection of near-duplicates in web video database. Proceedings of IEEE International Conference on Multimedia & Expo, pp. 293-296, 2008.
[16]H.-S. Kim, J. Lee, H. Liu, and D. Lee. Video linkage: group based copied video detection. Proceedings of International Conference on Content-Based Image and Video Retrieval, pp. 397-406, 2008.
[17]L. Bai, Y. Hu, S. Lao, A.F. Smeaton, and N.E. O’Connor. Automatic summarization of rushes video using bipartite graphs. Multimedia Tools and Applications, vol. 49, no. 1, pp. 63-80, 2010.
[18]Z. Zhang, Z.-N. Li, and M.S. Drew. Learning image similarities via probabilistic feature matching. Proceedings of IEEE International Conference on Image Processing, pp. 1857-1860, 2010.
[19]Y. Gao, Q. Dai, M. Wang, and N. Zhang. 3D model retrieval using weighted bipartite graph matching. Signal Processing: Image Communication, vol. 26, pp. 39-47, 2011.
[20]W.-T. Chu, C.-J. Li, and Y.-K. Chou. Tag suggestion and localization for web videos by bipartite graph matching. Proceeding of International ACM Workshop on Social Media, pp. 35-40, 2011.
[21]V. Kolesnikov, A.-R. Sadeghi, and T. Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In International Conference on Cryptology and Network Security. vol. 5888, pp. 1-20, 2009.
[22]Y. Huang, D. Evans, J. Katz, and L. Malka. Faster secure two-party computation using garbled circuits. In USENIX Security Symposium, pp.35-35, 2011.
[23]Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In Advances in Cryptology, vol. 2729, pp. 145-161, 2003.
[24]A. C. Yao. How to generate and exchange secrets. In IEEE Symposium on Foundations
of Computer Science, pp. 162–167, 1986.
[25]R. Lagendijk, Z. Erkin, and M. Barni, Encrypted signal processing for privacy protection, IEEE Signal Process. Mag., vol. 30, no. 1, pp. 82–105, 2013.
[26]B. Thomee, E.M. Bakker, and M.S. Lew. TOP-SURF: a visual words toolkit. Proceedings of ACM Multimedia Conference, pp. 1473-1476, 2010.
[27]J. Law-To, A. Joly, and N. Boujemaa. Muscle-VCD-2007: a live benchmark for video copy detection, 2007. http://www-rocq.inria.fr/imedia/civr-bench/.
[28]Sigma Knowledge Engineering Environment: http://sigmakee.sourceforge.net/
[29]A. Pease. The Sigma Ontology Development Environment, in Working Notes of the IJCAI-2003 Workshop on Ontology and Distributed Systems, 2003.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔