### Approximating Private Set Union/Intersection Cardinality with Logarithmic Complexity

Changyu Dong and Grigorios Loukides

##### Abstract

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.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. IEEE Transactions on Information Forensics and Security
DOI
10.1109/TIFS.2017.2721360
Keywords
Private Set Union CardinalityPrivate Set Intersection CardinalityPrivacy Preserving Data Mining
Contact author(s)
changyu dong @ gmail com
History
Short URL
https://ia.cr/2018/495

CC BY

BibTeX

@misc{cryptoeprint:2018/495,
author = {Changyu Dong and Grigorios Loukides},
title = {Approximating Private Set Union/Intersection Cardinality with Logarithmic Complexity},
howpublished = {Cryptology ePrint Archive, Paper 2018/495},
year = {2018},
doi = {10.1109/TIFS.2017.2721360},
note = {\url{https://eprint.iacr.org/2018/495}},
url = {https://eprint.iacr.org/2018/495}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.