Honest-Verifier Private Disjointness Testing without Random Oracles

Abstract. This paper presents an efficient construction of a private disjointness testing protocol that is secure against malicious provers and honest-but-curious (semi-honest) verifiers, without the use of random oracles. In a completely semi-honest setting, this construction implements a private intersection cardinality protocol. We formally define both private intersection cardinality and private disjointness testing protocols. The HW construction will be proven secure under the subgroup decision and subgroup computation assumptions. A major advantage of HW is that it does not require bilinear groups, random oracles, or non-interactive zero knowledge proofs. Applications of private intersection cardinality and disjointness testing protocols include privacy-preserving data mining and anonymous login systems