用於多媒體分析與檢索的隱私保護二元圖配對架構

A Privacy-Preserving Bipartite Graph Matching Framework for Multimedia Analysis and Retrieval

張豐麒(Feng-Chi Chang)

指導教授 ： 朱威達

國立中正大學/工學院/資訊工程學系/碩士(2013年)

摘要

雲端運算技術的興起，提供無限量的運算能力與儲存空間的環境，為多媒體分析與檢索的研究帶來新契機。然而使用者的隱私，例如搜尋的意圖，可能會洩漏給伺服器，也有可能會被外來的公司或個人惡意利用。本論文提出一個隱私保護的多媒體分析架構，基於被廣泛利用的二元圖配對(bipartite graph matching)，讓多媒體分析與檢索的技術能夠在加密域(encryption domain)下運作。本論文重點在於讓伺服器不知道使用者想要搜尋什麼，並希望能完善地利用伺服器的強大運算能力來幫忙使用者搜尋。為了完成二元圖的建構與配對，我們整合同態加密法(homomorphic encryption)與溝通機制，來處理在加密域下的權重計算與匈牙利演算法(Hungarian algorithm)。除此之外，我們利用亂碼電路(garbled circuit)讓二元圖配對演算法的運算更有效率。我們基於隱私保護的架構實作影片標註(video tag suggestion)與複製影片偵測(video copy detection)兩個應用，以及利用實驗結果證明在加密域下與在明文域下的效能並駕齊驅。
從不同的觀點來看，我們提出一個利用標籤分群的階層式架構，縮減挑選標籤的數量來降低運算時間。我們也提出新的互動式隱私保護機制，讓伺服器利用使用者回饋的資訊來改善系統效能。由於二元圖配對的普遍性，我們提出的架構能被認可並可利用於各種能保護隱私的多媒體檢索應用上。

關鍵字

匈牙利演算法 ； DGK加密法 ； Paillier加密法 ； 隱私保護 ； 二元圖配對 ； 亂碼電路

並列摘要

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.

並列關鍵字

The Hungarian algorithm ； The DGK cryptosystem ； The Paillier cryptosystem ； Privacy preserving ； Bipartite graph matching ； The garbled circuit

參考文獻

[3] R. Diestel. Graph Theory. Heidelberg, Springer, 2005.

[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.

[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.

[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.

[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.