Abstract
In a Private Matching (PM) scheme, the client C has a dataset X of m elements, and the server S has a dataset Y of n elements. The client C can learn the set intersection X∩Y without leaking any information to the server S. Previously, the most efficient PM scheme requires communication of complexity O∼(m+n), which increases linearly with n. This may not be efficient enough in Client-Server models because the server's dataset Y is usually large. In this paper, we propose a PM scheme based on Oblivious Transfer (OT) and universal hash function. Our scheme requires communication of complexity O∼(m· <sup>log2</sup> n). Thus, our scheme is especially suitable for Client-Server models. We show that our scheme becomes more efficient when <sup>log2</sup> ( <sup>mn)1+Δ</sup> =O∼nm for security parameter Δ>0. However, utilizing the universal hash function would cause a mismatch issue which affects the accuracy of the PM scheme. In addition, it leaks the server's information. Therefore, we define approximate PM by relaxing the definition of PM; it is proved to be almost as secure as a PM scheme in a Client-Server model with proper configurations. © 2014 Elsevier Inc. All rights reserved.