  Private Set Intersection (PSI) is a widely used protocol that enables two
parties to securely compute a function over the intersected part of their
shared datasets and has been a significant research focus over the years.
However, recent studies have highlighted its vulnerability to Set Membership
Inference Attacks (SMIA), where an adversary might deduce an individual's
membership by invoking multiple PSI protocols. This presents a considerable
risk, even in the most stringent versions of PSI, which only return the
cardinality of the intersection. This paper explores the evaluation of
anonymity within the PSI context. Initially, we highlight the reasons why
existing works fall short in measuring privacy leakage, and subsequently
propose two attack strategies that address these deficiencies. Furthermore, we
provide theoretical guarantees on the performance of our proposed methods. In
addition to these, we illustrate how the integration of auxiliary information,
such as the sum of payloads associated with members of the intersection
(PSI-SUM), can enhance attack efficiency. We conducted a comprehensive
performance evaluation of various attack strategies proposed utilizing two real
datasets. Our findings indicate that the methods we propose markedly enhance
attack efficiency when contrasted with previous research endeavors. {The
effective attacking implies that depending solely on existing PSI protocols may
not provide an adequate level of privacy assurance. It is recommended to
combine privacy-enhancing technologies synergistically to enhance privacy
protection even further.
