TY - GEN

T1 - Privacy preserving set intersection based on bilinear groups

AU - Sang, Yingpeng

AU - Shen, Hong

PY - 2008

Y1 - 2008

N2 - We propose a more efficient privacy preserving set intersection protocol which improves the previously known result by a factor of O(N) in both the computation and communication complexities (N is the number of parties in the protocol). Our protocol is obtained in the malicious model, in which we assume a probabilistic polynomial-time bounded adversary actively controls a fixed set of t (t < N=2) parties. We use a (t + 1;N)-threshold version of the Boneh-Goh-Nissim (BGN) cryptosystem whose underlying group supports bilinear maps. The BGN cryptosystem is generally used in applications where the plaintext space should be small, because there is still a Discrete Logarithm (DL) problem after the decryption. In our protocol the plaintext space can be as large as bounded by the security parameter τ, and the intractability of DL problem is utilized to protect the private datasets. Based on the bilinear map, we also construct some efficient non-interactive proofs. The security of our protocol can be reduced to the common intractable problems including the random oracle, subgroup decision and discrete logarithm problems. The computation complexity of our protocol is O(NS 2τ 3) (S is the cardinality of each party's dataset), and the communication complexity is O(NS 2τ) bits. A similar work by Kissner et al. (2006) needs O(N 2S 2τ 3) computation complexity and O(N 2S 2τ) communication complexity for the same level of correctness as ours.

AB - We propose a more efficient privacy preserving set intersection protocol which improves the previously known result by a factor of O(N) in both the computation and communication complexities (N is the number of parties in the protocol). Our protocol is obtained in the malicious model, in which we assume a probabilistic polynomial-time bounded adversary actively controls a fixed set of t (t < N=2) parties. We use a (t + 1;N)-threshold version of the Boneh-Goh-Nissim (BGN) cryptosystem whose underlying group supports bilinear maps. The BGN cryptosystem is generally used in applications where the plaintext space should be small, because there is still a Discrete Logarithm (DL) problem after the decryption. In our protocol the plaintext space can be as large as bounded by the security parameter τ, and the intractability of DL problem is utilized to protect the private datasets. Based on the bilinear map, we also construct some efficient non-interactive proofs. The security of our protocol can be reduced to the common intractable problems including the random oracle, subgroup decision and discrete logarithm problems. The computation complexity of our protocol is O(NS 2τ 3) (S is the cardinality of each party's dataset), and the communication complexity is O(NS 2τ) bits. A similar work by Kissner et al. (2006) needs O(N 2S 2τ 3) computation complexity and O(N 2S 2τ) communication complexity for the same level of correctness as ours.

KW - Bilinear groups

KW - Cryptographic protocol

KW - Non interactive zero-knowledge proof

KW - Privacy preservation

KW - Set intersection

UR - http://www.scopus.com/inward/record.url?scp=78650226497&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:78650226497

SN - 9781920682552

T3 - Conferences in Research and Practice in Information Technology Series

SP - 47

EP - 54

BT - Computer Science 2008 - Proceedings of the 31st Australasian Computer Science Conference, ACSC 2008

T2 - 31st Australasian Computer Science Conference, ACSC 2008

Y2 - 22 January 2008 through 25 January 2008

ER -