MDPPC: Efficient Scalable Multiparty Delegated PSI and PSI Cardinality

Private Set Intersection (PSI) is one of the most important functions in secure multiparty computation (MPC). PSI protocols have been a practical cryptographic primitive and there are many privacy-preserving applications based on PSI protocols such as computing conversion of advertising and distributed computation. Private Set Intersection Cardinality (PSI-CA) is a useful variant of PSI protocol. PSI and PSI-CA allow several parties, each holding a private set, to jointly compute the intersection and cardinality, respectively without leaking any additional information. Nowadays, most PSI protocols mainly focus on two-party settings, while in multiparty settings, parties are able to share more valuable information and thus more desirable. On the other hand, with the advent of cloud computing, delegating computation to an untrusted server becomes an interesting problem. However, most existing delegated PSI protocols are unable to efficiently scale to multiple clients. In order to solve these problems, this paper proposes MDPPC, an efficient PSI protocol which supports scalable multiparty delegated PSI and PSI-CA operations. Security analysis shows that MDPPC is secure against semi-honest adversaries and it allows any number of colluding clients. For 15 parties with set size of 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">20</sup> on server side and 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">16</sup> on clients side, MDPPC costs only 81 seconds in PSI and 80 seconds in PSI-CA, respectively. The experimental results show that MDPPC has high scalability.