King's College London

Research portal

Approximating Private Set Union/Intersection Cardinality with Logarithmic Complexity

Research output: Contribution to journalArticlepeer-review

Changyu Dong, Grigorios Loukidis

Original languageEnglish
Pages (from-to)2792-2806
JournalIEEE Transactions on Information Forensics and Security
Issue number11
Early online date28 Jun 2017
Accepted/In press20 Jun 2017
E-pub ahead of print28 Jun 2017
PublishedNov 2017


  • Approximating Private Set Union_DONG_Publishedonline28June2017_GREEN AAM

    TIFS_DongLoukides.pdf, 1.63 MB, application/pdf

    Uploaded date:01 Jul 2017

    Version:Accepted author manuscript

    (c) 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.

King's Authors


The computation of private set union/intersection cardinality (PSU-CA/PSI-CA) is one of the most intensively studied problems in Privacy Preserving Data Mining (PPDM). However, existing protocols are computationally too expensive to be employed in real-world PPDM applications. In response, we propose efficient approximate protocols, whose accuracy can be tuned according to application requirements. We first propose a two-party PSU-CA protocol based on Flajolet-Martin sketches. The protocol has logarithmic computational/communication complexity and relies mostly on symmetric key operations. Thus, it is much more efficient and scalable than existing protocols. In addition, our protocol can hide its output. This feature is necessary in PPDM applications, since the union cardinality is often an intermediate result that must not be disclosed. We then propose a two-party PSI-CA protocol, which is derived from the PSU-CA protocol with virtually no cost. Both our two-party protocols can be easily extended to the multiparty setting. We also design an efficient masking scheme for (1,n)-OT. The scheme is used in optimizing the two-party protocols and is of independent interest, since it can speed up (1,n)-OT significantly when n is large. Last, we show through experiments the effectiveness and efficiency of our protocols.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454