Practical Traceable Over-Threshold Multi-Party Private Set Intersection

Multi-Party Private Set Intersection (MP-PSI) with threshold enhances the flexibility of MP-PSI by disclosing elements present in at least $t$ participants' sets, rather than requiring elements to appear in all $n$ sets. In scenarios where each participant is responsible for its dataset, e.g., digital forensics, MP-PSI with threshold is expected to disclose both intersection elements and corresponding holders such that elements are traceable and hence the reliability of intersection is guaranteed. We refer to MP-PSI with threshold supporting traceability as Traceable Over-Threshold Multi-Party Private Set Intersection (T-OT-MP-PSI). However, research on such protocols remains limited, and the current solution is resistant to $t-2$ semi-honest participants at the cost of considerable computational overhead. In this paper, we propose two novel Traceable OT-MP-PSI protocols. The first protocol is the underlineEfficient underlineTraceable OT-MP-PSI (ET-OT-MP-PSI), which combines Shamir's secret sharing with oblivious programmable pseudorandom function, achieving significantly improved efficiency with resistance to at most $t-2$ semi-honest participants. The second one is the underlineSecurity-enhanced underlineTraceable OT-MP-PSI (ST-OT-MP-PSI), which achieves security against up to $n-1$ semi-honest participants by further leveraging oblivious linear evaluation protocol. Compared to the recent Traceable OT-MP-PSI protocol by Mahdavi et al., our protocols eliminate the security assumption that certain special parties do not collude and provide stronger security guarantees. We implemented our proposed protocols and conducted extensive experiments under various settings. We compared the performance of our protocols with that of Mahdavi et al.'s protocol. While our Traceable OT-MP-PSI protocols enhance security, experimental results demonstrate high efficiency. For instance, given 5 participants, with threshold of 3, and set sizes are $2^{14}$, our ET-OT-MP-PSI protocol is 15056$times$ faster, and the ST-OT-MP-PSI is 505$times$ faster, compared to Mahdavi et al.'s protocol.