Private matching protocols without error probability
Lihua Liu, Zhengjun Cao · 2011
A private matching scheme is a two-party protocol between a client Alice and a server Bob. Alice holds a set X and Bob holds a set Y. At the conclusion of the protocol, Alice learns the intersection X ∩ Y (and nothing more), while Bob gains no information at all. Private matching is a special problem that is at the heart of numerous data processing tasks in a variety of applications. In this paper, we investigate some earlier private matching schemes and remark that they can only ensure that Alice learns X' ∩ Y', where X' ∩ Y' is approximately equal to X ∩ Y. We then present two private matching schemes in the model of semi-honest adversary. Due to the bijection used in these schemes, the resulting intersection X' ∩ Y' is strictly equal to X ∩ Y.