Birds of a Feather Flock Together: How Set Bias Helps to Deanonymize You via Revealed Intersection Sizes


Xiaojie Guo, Ye Han, Zheli Liu, Ding Wang, and Yan Jia, Nankai University; Jin Li, Guangzhou University


Secure two-party protocols that compute intersection-related statistics have attracted much attention from the industry. These protocols enable two organizations to jointly compute a function (e.g., count and sum) over the intersection of their sets without explicitly revealing this intersection. However, most of such protocols will reveal the intersection size of the two sets in the end. In this work, we are interested in how well an attacker can leverage the revealed intersection sizes to infer some elements' membership of one organization's set. Even disclosing an element's membership of one organization's set to the other organization may violate privacy regulations (e.g., GDPR) since such an element is usually used to identify a person between two organizations. We are the first to study this set membership leakage in intersection-size-revealing protocols. We propose two attacks, namely, baseline attack and feature-aware attack, to evaluate this leakage in realistic scenarios. In particular, our feature-aware attack exploits the realistic set bias that elements with specific features are more likely to be the members of one organization's set. The results show that our two attacks can infer 2.0 ∼ 72.7 set members on average in three realistic scenarios. If the set bias is not weak, the feature-aware attack will outperform the baseline one. For example, in COVID-19 contact tracing, the feature-aware attack can find 25.9 tokens of infected patients in 135 protocol invocations, 1.5 × more than the baseline attack. We discuss how such results may cause negative real-world impacts and propose possible defenses against our attacks.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {281334,
author = {Xiaojie Guo and Ye Han and Zheli Liu and Ding Wang and Yan Jia and Jin Li},
title = {Birds of a Feather Flock Together: How Set Bias Helps to Deanonymize You via Revealed Intersection Sizes},
booktitle = {31st USENIX Security Symposium (USENIX Security 22)},
year = {2022},
isbn = {978-1-939133-31-1},
address = {Boston, MA},
pages = {1487--1504},
url = {},
publisher = {USENIX Association},
month = aug,

Presentation Video