Cryptology ePrint Archive: Report 2021/172

Efficient Linear Multiparty PSI and Extensions to Circuit/Quorum PSI

Nishanth Chandran and Nishka Dasgupta and Divya Gupta and Sai Lakshmi Bhavana Obbattu and Sruthi Sekar and Akash Shah

Abstract: Multiparty Private Set Intersection (mPSI), enables $n$ parties, each holding private sets (each of size $m$) to compute the intersection of these private sets, without revealing any other information to each other. While several protocols for this task are known, the only concretely efficient protocol is due to the work of Kolesnikov et al. (KMPRT, CCS 2017), who gave a semi-honest secure protocol with communication complexity $\mathcal{O}(nmt\lambda)$, where $t<n$ is the number of corrupt parties and $\lambda$ is the security parameter. In this work, we make the following contributions: $-$ First, for the natural adversarial setting of semi-honest honest majority (i.e. $t<n/2$), we asymptotically improve upon the above result and provide a concretely efficient protocol with total communication of $\mathcal{O}(nm\lambda)$. $-$ Second, concretely, our protocol has $6(t+2)/5$ times lesser communication than KMPRT and is upto $5\times$ and $6.2\times$ faster than KMPRT in the LAN and WAN setting even for 15 parties. $-$ Finally, we introduce and consider two important variants of mPSI - circuit PSI (that allows the parties to compute a function over the intersection set without revealing the intersection itself) and quorum PSI (that allows $P_1$ to learn all the elements in his/her set that are present in at least $k$ other sets) and provide concretely efficient protocols for these variants.

Category / Keywords: cryptographic protocols / secure multiparty computation, private set intersection, protocol security

Date: received 17 Feb 2021

Contact author: t-nidasg at microsoft com,sruthi sekar1@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210217:125712 (All versions of this report)

Short URL: ia.cr/2021/172


[ Cryptology ePrint archive ]