An Efficient-Communication Private Matching Scheme in Client-Server Model

在用戶端與伺服器架構底下的效率傳輸私密配對方法

羅艷華(Monica Law Chu)

指導教授 ： 孫宏民

國立清華大學/電機資訊學院/資訊系統與應用研究所/碩士(2010年)

摘要

In this thesis, we propose an efficient- communication solution for private matching problem in Client-Server model. We consider the Client-Server environment, the client C has the dataset X of m elements and Server S has the dataset of n elements. However, it has shown to be not efficient, because the client’s dataset is smaller than the server’s dataset, i.e., m << n. Previously, the best result for solving PM problem requires the communication complexity O (m + n), which is linearly increasing with n.
Our proposed scheme is based on Oblivious Transfer. The communication complexity will only require O (m • log2 n), which is linearly increasing with log2 n. The technology is to construct a small universe, called hashed universe, by applying the universal hash function to the based universe of X and Y. We show that running the PM protocol will output the same result both in the based universe and the hashed universe. Our proposed scheme can perform more efficient when log2 (m +n) = O (n/m), for some security parameter ∆ > 0. We have to point out that our method can control the Error probability of choosing a PM applicable function to be very small. Compared to the previous PM protocol, our method is much more communication-efficient in the Client-Server model.

關鍵字

私人匹配 ； 不經意傳輸 ； 通用散列函數 ； 通信複雜性

並列摘要

本論文的目標在找出一個有效率的傳輸複雜度再私密配對的方法。我們分析過去最好的方法為O(m+n)，其中m是伺服器端的資料個數，而n是用戶端的資料個數。然而，這在一般的用戶端與伺服器端的架構底下是很沒有效率的。一般來說，伺服器的資料個數遠遠大於用戶端的資料個數，這會使得私密配對的複雜度隨著n呈線性成長。
在本論文裡，我們提出一個有效率傳輸的私密配對方法。我們的方法尤其適用在用戶端與伺服器端架構底下。我們利用模糊傳輸協定(OT)的技巧去設計私密配對，並達到了O (m • log2 n)的傳輸複雜度。此外，我們並証明此方法在log2 (m +n) = O ( )會表現的比傳統的方法來的更有效率。我們採用 Universal hash function的技巧，將原本用戶端與伺服器端基於的資料集合X和Y映射到較小的資料集合，且經過由基於模糊傳輸協定的私密配對後，仍會有與原來配對X和Y相同的結果，因此達到具有傳輸效率的私密配對方法。

並列關鍵字

Private matching ； Oblivious Transfer ； Universal hash function ； Communication Complexity

參考文獻

[1] Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164

[6] Hazay, C., Lindell, Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 155-175. Springer, Heidelberg (2008).

[7] Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious psedorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303-324. Springer, Heidelberg (2005).

[9] Kiayias, A., and Mitrofanova, A. Testing disjointness of private datasets. In Financial Cryptography (2005), A. S. Patrick and M. Yung, Eds., vol. 3570 of Lecture Notes in Computer Science, Springer, pp. 109-124.

[11] Pascal Paillier, “Public Key Cryptosystems Based on Composite Degree Residuosity Class”, EUROCRYPT 1999, pp. 223-238.