Privacy preserving set intersection protocol secure against malicious behaviors

Abstract

When datasets are distributed on different sources, finding out their intersection while preserving the privacy of the datasets is a widely required task. In this paper, we address the privacy preserving set intersection (PPSI) problem, in which each of the N parties learns no elements other than the intersection of their N private datasets. We propose an efficient protocol in the malicious model, where the adversary may control arbitrary number of parties and execute the protocol for its own benefit. A related work in [12] has a correctness probability of ( v;1)ldquo (f is the size of the encryption scheme's plaintext space), a computation complexity of' 0(N2 S2lgf) (S is the size of each party's data set). Our PPSI protocol in the malicious model has a correctness probability iquest/C a-/1)JV~1 plusmnmiddotd achieves a computation cost of 0{c2S2lgM) (c is the number of malicious parties and c < N eurordquo I).