# American Institute of Mathematical Sciences

May  2021, 15(2): 365-386. doi: 10.3934/amc.2020071

## Secure and efficient multiparty private set intersection cardinality

 1 Department of Mathematics, National Institute of Technology Jamshedpur, Jamshedpur-831014, India 2 Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA 93943, USA 3 Department of Mathematics, The LNM Institute of Information Technology, Jaipur-302031, India

* Corresponding author: sdebnath.math@nitjsr.ac.in

Received  August 2019 Revised  February 2020 Published  April 2020

In the field of privacy preserving protocols, Private Set Intersection (PSI) plays an important role. In most of the cases, PSI allows two parties to securely determine the intersection of their private input sets, and no other information. In this paper, employing a Bloom filter, we propose a Multiparty Private Set Intersection Cardinality (MPSI-CA), where the number of participants in PSI is not limited to two. The security of our scheme is achieved in the standard model under the Decisional Diffie-Hellman (DDH) assumption against semi-honest adversaries. Our scheme is flexible in the sense that set size of one participant is independent from that of the others. We consider the number of modular exponentiations in order to determine computational complexity. In our construction, communication and computation overheads of each participant is $O(v_{\sf max}k)$ except that the complexity of the designated party is $O(v_1)$, where $v_{\sf max}$ is the maximum set size, $v_1$ denotes the set size of the designated party and $k$ is a security parameter. Particularly, our MSPI-CA is the first that incurs linear complexity in terms of set size, namely $O(nv_{\sf max}k)$, where $n$ is the number of participants. Further, we extend our MPSI-CA to MPSI retaining all the security attributes and other properties. As far as we are aware of, there is no other MPSI so far where individual computational cost of each participant is independent of the number of participants. Unlike MPSI-CA, our MPSI does not require any kind of broadcast channel as it uses star network topology in the sense that a designated party communicates with everyone else.

Citation: Sumit Kumar Debnath, Pantelimon Stǎnicǎ, Nibedita Kundu, Tanmay Choudhury. Secure and efficient multiparty private set intersection cardinality. Advances in Mathematics of Communications, 2021, 15 (2) : 365-386. doi: 10.3934/amc.2020071
##### References:

show all references

##### References:
Setup algorithm of our MPSI-CA
Interaction among parties in ${\mbox{MPSI-CA}\sf .request}$
Interaction among parties in ${\mbox{MPSI-CA}\sf .response}$
Interaction among parties in ${\mbox{MPSI-CA}\sf .computation}$
Interaction among parties in ${\mbox{MPSI} \sf .response}$
Interaction among parties in ${\mbox{MPSI} \sf .computation}$
Complexity of MPSI and MPSI-CA
 MPSI-CA Exp GE Hash Inv $P_1$ $v_1$ $2v_1$ $kv_1$ $v_1$ $P_i,i\neq 1$ $2m+3v_1$ $2m+3v_1$ $kv_i$ MPSI Exp GE Hash Inv $P_1$ $v_1$ $2(n-1)v_1$ $kv_1$ $v_1$ $P_i,i\neq 1$ $2m+v_1$ $2m+v_1$ $kv_i$ $v_i=$ set size of $P_i$, $m = \lceil\frac{kv_{\sf max}}{\ln 2}\rceil=$ optimal size of Bloom filter, $v_{\sf max} =$ maximum of $\{v_1, \ldots, v_n\}$
 MPSI-CA Exp GE Hash Inv $P_1$ $v_1$ $2v_1$ $kv_1$ $v_1$ $P_i,i\neq 1$ $2m+3v_1$ $2m+3v_1$ $kv_i$ MPSI Exp GE Hash Inv $P_1$ $v_1$ $2(n-1)v_1$ $kv_1$ $v_1$ $P_i,i\neq 1$ $2m+v_1$ $2m+v_1$ $kv_i$ $v_i=$ set size of $P_i$, $m = \lceil\frac{kv_{\sf max}}{\ln 2}\rceil=$ optimal size of Bloom filter, $v_{\sf max} =$ maximum of $\{v_1, \ldots, v_n\}$
Comparative summary of MPSI protocols
 Protocol Adv. Security Comm. Comp. Based model assumption on [46] Mal AHE $O(n^2v_{\sf max}^2)$ $O(n^2\log n v_{\sf max}^2)$ OPE [12] Mal DCR $O((nv_{\sf max} + 10v_{\sf max}\log^2v_{\sf max}))$ $O(nv_{\sf max}^2)$ MP [10] Mal AHE $O(nv_{\sf max}^2)$ $O(nv_{\sf max}^2)$ OPE [51] Mal DCR $O(n^2\log nv_{\sf max}^2)$ $O(\log nv_{\sf max}^2)$ OPE [52] Mal SD $O(nv_{\sf max}^2)$ $O(nv_{\sf max}^2)$ BG [49] SH DDH $O(nv_{\sf max})$ $D:O(nv_{\sf max}); P_i:O(v_{\sf max})$ BF Sch. 1[39] SH DDH $O(nv_{\sf max}\kappa)$ $D:O(nv_{\sf max}^2\kappa); P_i:O(v_{\sf max}\kappa)$ OPE Sch. 2[39] Mal DDH $O((n^2+nv_{\sf max}+nw\log v_{\sf max})\kappa)$ $D:O(nv_{\sf max}^2\kappa); P_i:O(v_{\sf max}\kappa)$ OPE [47] SH $O(nv_{\sf max}\kappa)$ $D:O(n\lambda); P_i:O(t\lambda)$ OPRF Our SH DDH $O(nv_{\sf max}k)$ $D:O(v_1); P_i:O(v_{\sf max}k)$ BF OPE= Oblivious Polynomial Evaluation, MP= Multivariate Polynomials, BF= Bloom Filter, SD= Subgroup Decision, BG= Bilinear Group, Mal= Malicious, AHE= Additively Homomorphic Encryption, DDH=Decisional Diffie-Hellman, DCR=Decisional Quadratic Residuosity, SH=Semi-honest, OPRF= Oblivious Pseudorandom Function, $D$= designated party, $P_i$= participants other than designated party, $n$= number of participants, $v_1$= set size of the designated party $D$, $t$= number of dishonestly colluding participants, $v_{\sf max}$= maximum set size, $\kappa, k, \lambda$= security parameters.
 Protocol Adv. Security Comm. Comp. Based model assumption on [46] Mal AHE $O(n^2v_{\sf max}^2)$ $O(n^2\log n v_{\sf max}^2)$ OPE [12] Mal DCR $O((nv_{\sf max} + 10v_{\sf max}\log^2v_{\sf max}))$ $O(nv_{\sf max}^2)$ MP [10] Mal AHE $O(nv_{\sf max}^2)$ $O(nv_{\sf max}^2)$ OPE [51] Mal DCR $O(n^2\log nv_{\sf max}^2)$ $O(\log nv_{\sf max}^2)$ OPE [52] Mal SD $O(nv_{\sf max}^2)$ $O(nv_{\sf max}^2)$ BG [49] SH DDH $O(nv_{\sf max})$ $D:O(nv_{\sf max}); P_i:O(v_{\sf max})$ BF Sch. 1[39] SH DDH $O(nv_{\sf max}\kappa)$ $D:O(nv_{\sf max}^2\kappa); P_i:O(v_{\sf max}\kappa)$ OPE Sch. 2[39] Mal DDH $O((n^2+nv_{\sf max}+nw\log v_{\sf max})\kappa)$ $D:O(nv_{\sf max}^2\kappa); P_i:O(v_{\sf max}\kappa)$ OPE [47] SH $O(nv_{\sf max}\kappa)$ $D:O(n\lambda); P_i:O(t\lambda)$ OPRF Our SH DDH $O(nv_{\sf max}k)$ $D:O(v_1); P_i:O(v_{\sf max}k)$ BF OPE= Oblivious Polynomial Evaluation, MP= Multivariate Polynomials, BF= Bloom Filter, SD= Subgroup Decision, BG= Bilinear Group, Mal= Malicious, AHE= Additively Homomorphic Encryption, DDH=Decisional Diffie-Hellman, DCR=Decisional Quadratic Residuosity, SH=Semi-honest, OPRF= Oblivious Pseudorandom Function, $D$= designated party, $P_i$= participants other than designated party, $n$= number of participants, $v_1$= set size of the designated party $D$, $t$= number of dishonestly colluding participants, $v_{\sf max}$= maximum set size, $\kappa, k, \lambda$= security parameters.
Comparative summary of MPSI-CA protocols
 Protocol Adv. Security Comm. Comp. Based model assumption on [46] SH AHE $O(n^2v_{\sf max})$ $O(n^2v_{\sf max}^2)$ OPE Our SH DDH $O(nv_{\sf max}k)$ $D:O(v_1); P_i:O(v_{\sf max}k)$ BF OPE= Oblivious Polynomial Evaluation, BF= Bloom Filter, SH=Semi-honest, AHE= Additively Homomorphic Encryption, DDH=Decisional Diffie-Hellman, $D$= designated party, $P_i$= participants other than designated party, $n$= number of participants, $v_1$= set size of the designated party $D$, $v_{\sf max}$= maximum set size.
 Protocol Adv. Security Comm. Comp. Based model assumption on [46] SH AHE $O(n^2v_{\sf max})$ $O(n^2v_{\sf max}^2)$ OPE Our SH DDH $O(nv_{\sf max}k)$ $D:O(v_1); P_i:O(v_{\sf max}k)$ BF OPE= Oblivious Polynomial Evaluation, BF= Bloom Filter, SH=Semi-honest, AHE= Additively Homomorphic Encryption, DDH=Decisional Diffie-Hellman, $D$= designated party, $P_i$= participants other than designated party, $n$= number of participants, $v_1$= set size of the designated party $D$, $v_{\sf max}$= maximum set size.
 [1] Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1499-1529. doi: 10.3934/dcdsb.2020170 [2] Buddhadev Pal, Pankaj Kumar. A family of multiply warped product semi-Riemannian Einstein metrics. Journal of Geometric Mechanics, 2020, 12 (4) : 553-562. doi: 10.3934/jgm.2020017 [3] Xiaoming Wang. Upper semi-continuity of stationary statistical properties of dissipative systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 521-540. doi: 10.3934/dcds.2009.23.521 [4] Qianqian Hou, Tai-Chia Lin, Zhi-An Wang. On a singularly perturbed semi-linear problem with Robin boundary conditions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 401-414. doi: 10.3934/dcdsb.2020083 [5] Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012 [6] Mingjun Zhou, Jingxue Yin. Continuous subsonic-sonic flows in a two-dimensional semi-infinitely long nozzle. Electronic Research Archive, , () : -. doi: 10.3934/era.2020122 [7] Xin Zhao, Tao Feng, Liang Wang, Zhipeng Qiu. Threshold dynamics and sensitivity analysis of a stochastic semi-Markov switched SIRS epidemic model with nonlinear incidence and vaccination. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021010 [8] Bing Sun, Liangyun Chen, Yan Cao. On the universal $\alpha$-central extensions of the semi-direct product of Hom-preLie algebras. Electronic Research Archive, , () : -. doi: 10.3934/era.2021004 [9] Karol Mikula, Jozef Urbán, Michal Kollár, Martin Ambroz, Ivan Jarolímek, Jozef Šibík, Mária Šibíková. Semi-automatic segmentation of NATURA 2000 habitats in Sentinel-2 satellite images by evolving open curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1033-1046. doi: 10.3934/dcdss.2020231 [10] Guoliang Zhang, Shaoqin Zheng, Tao Xiong. A conservative semi-Lagrangian finite difference WENO scheme based on exponential integrator for one-dimensional scalar nonlinear hyperbolic equations. Electronic Research Archive, 2021, 29 (1) : 1819-1839. doi: 10.3934/era.2020093

2019 Impact Factor: 0.734