# 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  May 2021 Early access  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:
 [1] R. Agrawal, A. Evfimievski and R. Srikant, Information sharing across private databases, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, ACM, (2003), 86-97.  doi: 10.1145/872757.872771. [2] B. H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, 13 (1970), 422-426.  doi: 10.1145/362686.362692. [3] D. Boneh, The decision Diffie-Hellman problem, Algorithmic Number Theory, Springer, Lecture Notes in Comput. Sci., Springer, Berlin, 1423 (1998), 48-63.  doi: 10.1007/BFb0054851. [4] P. Bose, H. Guo, E. Kranakis, A. Maheshwari, P. Morin, J. Morrison, M. Smid and Y. H. Tang, On the false-positive rate of Bloom filters, Inform. Proc. Lett., 108 (2008), 210-213.  doi: 10.1016/j.ipl.2008.05.018. [5] J. Camenisch and V. Shoup, Practical verifiable encryption and decryption of discrete logarithms, Advances in Cryptology—CRYPTO 2003, Lecture Notes in Comput. Sci., Springer, Berlin, 2729 (2003), 126-144.  doi: 10.1007/978-3-540-45146-4_8. [6] J. Camenisch and M. Stadler, Proof Systems for General Statements about Discrete Logarithms, 1997. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1208. [7] J. Camenisch and G. M. Zaverucha, Private intersection of certified sets, Financial Cryptography and Data Security, Springer, (2009), 108-127.  doi: 10.1007/978-3-642-03549-4_7. [8] A. Cerulli, E. De Cristofaro and C. Soriente, Nothing refreshes like a RePSI: Reactive private set intersection, Applied Cryptography and Network Security, Lecture Notes in Comput. Sci., Springer, Cham, 10892 (2018), 280-300.  doi: 10.1007/978-3-319-93387-0_15. [9] H. Chen, K. Laine and P. Rindal, Fast private set intersection from homomorphic encryption, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ACM, (2017), 1243-1255.  doi: 10.1145/3133956.3134061. [10] J. H. Cheon, S. Jarecki and J. H. Seo, Multi-party privacy-preserving set intersection with quasi-linear complexity, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 95 (2012), 1366-1378.  doi: 10.1587/transfun.E95.A.1366. [11] M. Ciampi and C. Orlandi, Combining private set-intersection with secure two-party computation, Security and Cryptography for Networks, Lecture Notes in Comput. Sci., Springer, Cham, 11035 (2018), 464-482.  doi: 10.1007/978-3-319-98113-0. [12] D. Dachman-Soled, T. Malkin, M. Raykova and M. Yung, Secure efficient multiparty computing of multivariate polynomials and applications, Applied Cryptography and Network Security, (2011), 130-146.  doi: 10.1007/978-3-642-21554-4_8. [13] A. Davidson and C. Cid, An efficient toolkit for computing private set operations, Information Security and Privacy - ACISP, (2017), 261-278.  doi: 10.1007/978-3-319-59870-3_15. [14] E. De Cristofaro, P. Gasti and G. Tsudik, Fast and private computation of cardinality of set intersection and union, Cryptology and Network Security, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7712 (2012), 218-231.  doi: 10.1007/978-3-642-35404-5_17. [15] E. De Cristofaro, J. Kim and G. Tsudik, Linear-complexity private set intersection protocols secure in malicious model, Adv. in Cryptology - ASIACRYPT, Springer, (2010), 213-231. [16] E. De Cristofaro and G. Tsudik, Practical private set intersection protocols with linear complexity, Financial Cryptography and Data Security, (2010), 143-159.  doi: 10.1007/978-3-642-14577-3_13. [17] E. De Cristofaro and G. Tsudik, Experimenting with fast private set intersection, Trust and Trustworthy Computing, (2012), 55-73.  doi: 10.1007/978-3-642-30921-2_4. [18] S. K. Debnath and R. Dutta, Efficient private set intersection cardinality in the presence of malicious adversaries, Provable Security, Lecture Notes in Comput. Sci., Springer, Cham, 9451 (2015), 326-339.  doi: 10.1007/978-3-319-26059-4_18. [19] S. K. Debnath and R. Dutta, Secure and efficient private set intersection cardinality using Bloom filter, International Information Security Conference, Springer, (2015), 209-226. [20] S. K. Debnath and R. Dutta, How to meet big data when private set intersection realizes constant communication complexity, Information and Communications Security, Springer, (2016), 445-454.  doi: 10.1007/978-3-319-50011-9_34. [21] S. K. Debnath and R. Dutta, New realizations of efficient and secure private set intersection protocols preserving fairness, Information Security and Cryptology—ICISC 2016, Lecture Notes in Comput. Sci., Springer, Cham, 10157 (2017), 254-284.  doi: 10.1007/978-3-319-53177-9_14. [22] S. K. Debnath and R. Dutta, Provably secure fair mutual private set intersection cardinality utilizing Bloom filter, Information Security and Cryptology, Lecture Notes in Comput. Sci., Springer, Cham, 10143 (2017), 505-525. [23] S. K. Debnath and R. Dutta, Towards fair mutual private set intersection with linear complexity, Security Comm. Networks, 9 (2016), 1589-1612.  doi: 10.1002/sec.1450. [24] Y. Desmedt and Y. Frankel, Threshold cryptosystems, Adv. in Cryptology - CRYPTO 89, Springer, (1990), 307-315. [25] C. Y. Dong, L. Q. Chen, J. Camenisch and G. Russello, Fair private set intersection with a semi-trusted arbiter, Data and Applications Security and Privacy XXVII, Springer, (2013), 128-144.  doi: 10.1007/978-3-642-39256-6_9. [26] C. Y. Dong, L. Q. Chen and Z. K. Wen, When private set intersection meets big data: An efficient and scalable protocol, Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, ACM, (2013), 789-800.  doi: 10.1145/2508859.2516701. [27] C. Y. Dong and G. Loukides, Approximating private set union/intersection cardinality with logarithmic complexity, IEEE Transactions on Information Forensics and Security, 12 (2017), 2792-2806.  doi: 10.1109/TIFS.2017.2721360. [28] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory, 31 (1985), 469-472.  doi: 10.1109/TIT.1985.1057074. [29] B. H. Falk, D. Noble and R. Ostrovsky, Private set intersection with linear communication from general assumptions, (2018). [30] P. Flajolet and G. N. Martin., Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, 31 (1985), 182-209.  doi: 10.1016/0022-0000(85)90041-8. [31] M. J. Freedman, C. Hazay, K. Nissim and B. Pinkas, Efficient set intersection with simulation-based security, Journal of Cryptology, 29 (2016), 115-155.  doi: 10.1007/s00145-014-9190-0. [32] M. J. Freedman, K. Nissim and B. Pinkas, Efficient private matching and set intersection, Advances in Cryptology—EUROCRYPT 2004, Lecture Notes in Comput. Sci., Springer, Berlin, 3027 (2004), 1-19.  doi: 10.1007/978-3-540-24676-3_1. [33] J. Furukawa, Efficient and verifiable shuffling and shuffle-decryption, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 88 (2005), 172-188. [34] O. Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, 2009. [35] S. Goldwasser and S. Micali, Probabilistic encryption, Journal of Computer and System Sciences, 28 (1984), 270-299.  doi: 10.1016/0022-0000(84)90070-9. [36] C. Hazay, Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs, Theory of Cryptography, Part II, Lecture Notes in Comput. Sci., Springer, Heidelberg, 9015 (2015), 90-120.  doi: 10.1007/978-3-662-46497-7_4. [37] C. Hazay and Y. Lindell, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, Theory of Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 4948 (2008), 155-175.  doi: 10.1007/978-3-540-78524-8_10. [38] C. Hazay and K. Nissim, Efficient set operations in the presence of malicious adversaries, Public Key Cryptography - PKC, Lecture Notes in Comput. Sci., Springer, Berlin, 6056 (2010), 312-331.  doi: 10.1007/978-3-642-13013-7_19. [39] C. Hazay and M. Venkitasubramaniam, Scalable multi-party private set-intersection, Public-Key Cryptography—PKC 2017, Part I, Lecture Notes in Comput. Sci., Springer, Berlin, 10174 (2017), 175-203.  doi: 10.1007/978-3-662-54365-8_8. [40] S. Hohenberger and S. A. Weis, Honest-verifier private disjointness testing without random oracles, Privacy Enhancing Technologies, Springer, (2006), 277-294.  doi: 10.1007/11957454_16. [41] Y. Huang, D. Evans and J. Katz, Private set intersection: Are garbled circuits better than custom protocols, Network and Distributed System Security Symposium (NDSS), The Internet Society, (2012). [42] S. Jarecki and X. M. Liu, Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, Theory of Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 5444 (2009), 577-594.  doi: 10.1007/978-3-642-00457-5_34. [43] S. Jarecki and X. M. Liu, Fast secure computation of set intersection, Security and Cryptography for Networks, Springer, (2010), 418-435.  doi: 10.1007/978-3-642-15317-4_26. [44] F. Kerschbaum, Outsourced private set intersection using homomorphic encryption, Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, ACM, (2012), 85-86.  doi: 10.1145/2414456.2414506. [45] Á. Kiss, J. Liu, T. Schneider, N. Asokan and B. Pinkas, Private set intersection for unequal set sizes with mobile applications, Proceedings on Privacy Enhancing Technologies, 2017 (2017), 177-197.  doi: 10.1515/popets-2017-0044. [46] L. Kissner and D. Song, Privacy-preserving set operations, Adv. in Cryptology - CRYPTO 2005, Lecture Notes in Comput. Sci., Springer, Berlin, 3621 (2005), 241-257.  doi: 10.1007/11535218_15. [47] V. Kolesnikov, N. Matania, B. Pinkas, M. Rosulek and N. Trieu, Practical multi-party private set intersection from symmetric-key techniques, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ACM, (2017), 1257-1272.  doi: 10.1145/3133956.3134065. [48] D. Many, M. Burkhart and X. Dimitropoulos, Fast private set operations with sepia, Technical Report 345, Mar, Tech. Rep., (2012). [49] A. Miyaji and S. Nishida, A scalable multiparty private set intersection, International Conference on Network and System Security, Springer, (2015), 376-385. [50] P. Rindal and M. Rosulek, Malicious-secure private set intersection via dual execution, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ACM, (2017), 1229-1242.  doi: 10.1145/3133956.3134044. [51] Y. P. Sang and H. Shen, Privacy preserving set intersection protocol secure against malicious behaviors, Parallel and Distributed Computing, Applications and Technologies (PDCAT), IEEE International Conference on, (2007), 461-468.  doi: 10.1109/PDCAT.2007.59. [52] Y. Sang and H. Shen, Privacy preserving set intersection based on bilinear groups, Proceedings of the Thirty-First Australasian Conference on Computer Science, Australian Computer Society, Inc., 74 (2008), 47-54. [53] R.-H. Shi, Y. Mu, H. Zhong, S. Zhang and J. Cui, Quantum private set intersection cardinality and its application to anonymous authentication, 370/371, (2016), 147-158.  doi: 10.1016/j.ins.2016.07.071.

show all references

##### References:
 [1] R. Agrawal, A. Evfimievski and R. Srikant, Information sharing across private databases, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, ACM, (2003), 86-97.  doi: 10.1145/872757.872771. [2] B. H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, 13 (1970), 422-426.  doi: 10.1145/362686.362692. [3] D. Boneh, The decision Diffie-Hellman problem, Algorithmic Number Theory, Springer, Lecture Notes in Comput. Sci., Springer, Berlin, 1423 (1998), 48-63.  doi: 10.1007/BFb0054851. [4] P. Bose, H. Guo, E. Kranakis, A. Maheshwari, P. Morin, J. Morrison, M. Smid and Y. H. Tang, On the false-positive rate of Bloom filters, Inform. Proc. Lett., 108 (2008), 210-213.  doi: 10.1016/j.ipl.2008.05.018. [5] J. Camenisch and V. Shoup, Practical verifiable encryption and decryption of discrete logarithms, Advances in Cryptology—CRYPTO 2003, Lecture Notes in Comput. Sci., Springer, Berlin, 2729 (2003), 126-144.  doi: 10.1007/978-3-540-45146-4_8. [6] J. Camenisch and M. Stadler, Proof Systems for General Statements about Discrete Logarithms, 1997. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1208. [7] J. Camenisch and G. M. Zaverucha, Private intersection of certified sets, Financial Cryptography and Data Security, Springer, (2009), 108-127.  doi: 10.1007/978-3-642-03549-4_7. [8] A. Cerulli, E. De Cristofaro and C. Soriente, Nothing refreshes like a RePSI: Reactive private set intersection, Applied Cryptography and Network Security, Lecture Notes in Comput. Sci., Springer, Cham, 10892 (2018), 280-300.  doi: 10.1007/978-3-319-93387-0_15. [9] H. Chen, K. Laine and P. Rindal, Fast private set intersection from homomorphic encryption, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ACM, (2017), 1243-1255.  doi: 10.1145/3133956.3134061. [10] J. H. Cheon, S. Jarecki and J. H. Seo, Multi-party privacy-preserving set intersection with quasi-linear complexity, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 95 (2012), 1366-1378.  doi: 10.1587/transfun.E95.A.1366. [11] M. Ciampi and C. Orlandi, Combining private set-intersection with secure two-party computation, Security and Cryptography for Networks, Lecture Notes in Comput. Sci., Springer, Cham, 11035 (2018), 464-482.  doi: 10.1007/978-3-319-98113-0. [12] D. Dachman-Soled, T. Malkin, M. Raykova and M. Yung, Secure efficient multiparty computing of multivariate polynomials and applications, Applied Cryptography and Network Security, (2011), 130-146.  doi: 10.1007/978-3-642-21554-4_8. [13] A. Davidson and C. Cid, An efficient toolkit for computing private set operations, Information Security and Privacy - ACISP, (2017), 261-278.  doi: 10.1007/978-3-319-59870-3_15. [14] E. De Cristofaro, P. Gasti and G. Tsudik, Fast and private computation of cardinality of set intersection and union, Cryptology and Network Security, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7712 (2012), 218-231.  doi: 10.1007/978-3-642-35404-5_17. [15] E. De Cristofaro, J. Kim and G. Tsudik, Linear-complexity private set intersection protocols secure in malicious model, Adv. in Cryptology - ASIACRYPT, Springer, (2010), 213-231. [16] E. De Cristofaro and G. Tsudik, Practical private set intersection protocols with linear complexity, Financial Cryptography and Data Security, (2010), 143-159.  doi: 10.1007/978-3-642-14577-3_13. [17] E. De Cristofaro and G. Tsudik, Experimenting with fast private set intersection, Trust and Trustworthy Computing, (2012), 55-73.  doi: 10.1007/978-3-642-30921-2_4. [18] S. K. Debnath and R. Dutta, Efficient private set intersection cardinality in the presence of malicious adversaries, Provable Security, Lecture Notes in Comput. Sci., Springer, Cham, 9451 (2015), 326-339.  doi: 10.1007/978-3-319-26059-4_18. [19] S. K. Debnath and R. Dutta, Secure and efficient private set intersection cardinality using Bloom filter, International Information Security Conference, Springer, (2015), 209-226. [20] S. K. Debnath and R. Dutta, How to meet big data when private set intersection realizes constant communication complexity, Information and Communications Security, Springer, (2016), 445-454.  doi: 10.1007/978-3-319-50011-9_34. [21] S. K. Debnath and R. Dutta, New realizations of efficient and secure private set intersection protocols preserving fairness, Information Security and Cryptology—ICISC 2016, Lecture Notes in Comput. Sci., Springer, Cham, 10157 (2017), 254-284.  doi: 10.1007/978-3-319-53177-9_14. [22] S. K. Debnath and R. Dutta, Provably secure fair mutual private set intersection cardinality utilizing Bloom filter, Information Security and Cryptology, Lecture Notes in Comput. Sci., Springer, Cham, 10143 (2017), 505-525. [23] S. K. Debnath and R. Dutta, Towards fair mutual private set intersection with linear complexity, Security Comm. Networks, 9 (2016), 1589-1612.  doi: 10.1002/sec.1450. [24] Y. Desmedt and Y. Frankel, Threshold cryptosystems, Adv. in Cryptology - CRYPTO 89, Springer, (1990), 307-315. [25] C. Y. Dong, L. Q. Chen, J. Camenisch and G. Russello, Fair private set intersection with a semi-trusted arbiter, Data and Applications Security and Privacy XXVII, Springer, (2013), 128-144.  doi: 10.1007/978-3-642-39256-6_9. [26] C. Y. Dong, L. Q. Chen and Z. K. Wen, When private set intersection meets big data: An efficient and scalable protocol, Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, ACM, (2013), 789-800.  doi: 10.1145/2508859.2516701. [27] C. Y. Dong and G. Loukides, Approximating private set union/intersection cardinality with logarithmic complexity, IEEE Transactions on Information Forensics and Security, 12 (2017), 2792-2806.  doi: 10.1109/TIFS.2017.2721360. [28] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory, 31 (1985), 469-472.  doi: 10.1109/TIT.1985.1057074. [29] B. H. Falk, D. Noble and R. Ostrovsky, Private set intersection with linear communication from general assumptions, (2018). [30] P. Flajolet and G. N. Martin., Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, 31 (1985), 182-209.  doi: 10.1016/0022-0000(85)90041-8. [31] M. J. Freedman, C. Hazay, K. Nissim and B. Pinkas, Efficient set intersection with simulation-based security, Journal of Cryptology, 29 (2016), 115-155.  doi: 10.1007/s00145-014-9190-0. [32] M. J. Freedman, K. Nissim and B. Pinkas, Efficient private matching and set intersection, Advances in Cryptology—EUROCRYPT 2004, Lecture Notes in Comput. Sci., Springer, Berlin, 3027 (2004), 1-19.  doi: 10.1007/978-3-540-24676-3_1. [33] J. Furukawa, Efficient and verifiable shuffling and shuffle-decryption, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 88 (2005), 172-188. [34] O. Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, 2009. [35] S. Goldwasser and S. Micali, Probabilistic encryption, Journal of Computer and System Sciences, 28 (1984), 270-299.  doi: 10.1016/0022-0000(84)90070-9. [36] C. Hazay, Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs, Theory of Cryptography, Part II, Lecture Notes in Comput. Sci., Springer, Heidelberg, 9015 (2015), 90-120.  doi: 10.1007/978-3-662-46497-7_4. [37] C. Hazay and Y. Lindell, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, Theory of Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 4948 (2008), 155-175.  doi: 10.1007/978-3-540-78524-8_10. [38] C. Hazay and K. Nissim, Efficient set operations in the presence of malicious adversaries, Public Key Cryptography - PKC, Lecture Notes in Comput. Sci., Springer, Berlin, 6056 (2010), 312-331.  doi: 10.1007/978-3-642-13013-7_19. [39] C. Hazay and M. Venkitasubramaniam, Scalable multi-party private set-intersection, Public-Key Cryptography—PKC 2017, Part I, Lecture Notes in Comput. Sci., Springer, Berlin, 10174 (2017), 175-203.  doi: 10.1007/978-3-662-54365-8_8. [40] S. Hohenberger and S. A. Weis, Honest-verifier private disjointness testing without random oracles, Privacy Enhancing Technologies, Springer, (2006), 277-294.  doi: 10.1007/11957454_16. [41] Y. Huang, D. Evans and J. Katz, Private set intersection: Are garbled circuits better than custom protocols, Network and Distributed System Security Symposium (NDSS), The Internet Society, (2012). [42] S. Jarecki and X. M. Liu, Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, Theory of Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 5444 (2009), 577-594.  doi: 10.1007/978-3-642-00457-5_34. [43] S. Jarecki and X. M. Liu, Fast secure computation of set intersection, Security and Cryptography for Networks, Springer, (2010), 418-435.  doi: 10.1007/978-3-642-15317-4_26. [44] F. Kerschbaum, Outsourced private set intersection using homomorphic encryption, Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, ACM, (2012), 85-86.  doi: 10.1145/2414456.2414506. [45] Á. Kiss, J. Liu, T. Schneider, N. Asokan and B. Pinkas, Private set intersection for unequal set sizes with mobile applications, Proceedings on Privacy Enhancing Technologies, 2017 (2017), 177-197.  doi: 10.1515/popets-2017-0044. [46] L. Kissner and D. Song, Privacy-preserving set operations, Adv. in Cryptology - CRYPTO 2005, Lecture Notes in Comput. Sci., Springer, Berlin, 3621 (2005), 241-257.  doi: 10.1007/11535218_15. [47] V. Kolesnikov, N. Matania, B. Pinkas, M. Rosulek and N. Trieu, Practical multi-party private set intersection from symmetric-key techniques, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ACM, (2017), 1257-1272.  doi: 10.1145/3133956.3134065. [48] D. Many, M. Burkhart and X. Dimitropoulos, Fast private set operations with sepia, Technical Report 345, Mar, Tech. Rep., (2012). [49] A. Miyaji and S. Nishida, A scalable multiparty private set intersection, International Conference on Network and System Security, Springer, (2015), 376-385. [50] P. Rindal and M. Rosulek, Malicious-secure private set intersection via dual execution, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ACM, (2017), 1229-1242.  doi: 10.1145/3133956.3134044. [51] Y. P. Sang and H. Shen, Privacy preserving set intersection protocol secure against malicious behaviors, Parallel and Distributed Computing, Applications and Technologies (PDCAT), IEEE International Conference on, (2007), 461-468.  doi: 10.1109/PDCAT.2007.59. [52] Y. Sang and H. Shen, Privacy preserving set intersection based on bilinear groups, Proceedings of the Thirty-First Australasian Conference on Computer Science, Australian Computer Society, Inc., 74 (2008), 47-54. [53] R.-H. Shi, Y. Mu, H. Zhong, S. Zhang and J. Cui, Quantum private set intersection cardinality and its application to anonymous authentication, 370/371, (2016), 147-158.  doi: 10.1016/j.ins.2016.07.071.
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] Sara D. Cardell, Amparo Fúster-Sabater. Modelling the shrinking generator in terms of linear CA. Advances in Mathematics of Communications, 2016, 10 (4) : 797-809. doi: 10.3934/amc.2016041 [2] Alena Erchenko. Flexibility of Lyapunov exponents for expanding circle maps. Discrete and Continuous Dynamical Systems, 2019, 39 (5) : 2325-2342. doi: 10.3934/dcds.2019098 [3] Hideo Ikeda, Masayasu Mimura, Tommaso Scotti. Shadow system approach to a plankton model generating harmful algal bloom. Discrete and Continuous Dynamical Systems, 2017, 37 (2) : 829-858. doi: 10.3934/dcds.2017034 [4] F. Zeyenp Sargut, H. Edwin Romeijn. Capacitated requirements planning with pricing flexibility and general cost and revenue functions. Journal of Industrial and Management Optimization, 2007, 3 (1) : 87-98. doi: 10.3934/jimo.2007.3.87 [5] Sebastian Reich, Seoleun Shin. On the consistency of ensemble transform filter formulations. Journal of Computational Dynamics, 2014, 1 (1) : 177-189. doi: 10.3934/jcd.2014.1.177 [6] Alexander Bibov, Heikki Haario, Antti Solonen. Stabilized BFGS approximate Kalman filter. Inverse Problems and Imaging, 2015, 9 (4) : 1003-1024. doi: 10.3934/ipi.2015.9.1003 [7] Russell Johnson, Carmen Núñez. The Kalman-Bucy filter revisited. Discrete and Continuous Dynamical Systems, 2014, 34 (10) : 4139-4153. doi: 10.3934/dcds.2014.34.4139 [8] Jin-Won Kim, Amirhossein Taghvaei, Yongxin Chen, Prashant G. Mehta. Feedback particle filter for collective inference. Foundations of Data Science, 2021, 3 (3) : 543-561. doi: 10.3934/fods.2021018 [9] Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088 [10] Qiyu Jin, Ion Grama, Quansheng Liu. Convergence theorems for the Non-Local Means filter. Inverse Problems and Imaging, 2018, 12 (4) : 853-881. doi: 10.3934/ipi.2018036 [11] Hai Huyen Dam, Kok Lay Teo. Variable fractional delay filter design with discrete coefficients. Journal of Industrial and Management Optimization, 2016, 12 (3) : 819-831. doi: 10.3934/jimo.2016.12.819 [12] Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337 [13] Xueling Zhou, Bingo Wing-Kuen Ling, Hai Huyen Dam, Kok-Lay Teo. Optimal design of window functions for filter window bank. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1119-1145. doi: 10.3934/jimo.2020014 [14] Anugu Sumith Reddy, Amit Apte. Stability of non-linear filter for deterministic dynamics. Foundations of Data Science, 2021, 3 (3) : 647-675. doi: 10.3934/fods.2021025 [15] Andreas Bock, Colin J. Cotter. Learning landmark geodesics using the ensemble Kalman filter. Foundations of Data Science, 2021, 3 (4) : 701-727. doi: 10.3934/fods.2021020 [16] Valerii Maltsev, Michael Pokojovy. On a parabolic-hyperbolic filter for multicolor image noise reduction. Evolution Equations and Control Theory, 2016, 5 (2) : 251-272. doi: 10.3934/eect.2016004 [17] Kody Law, Abhishek Shukla, Andrew Stuart. Analysis of the 3DVAR filter for the partially observed Lorenz'63 model. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 1061-1078. doi: 10.3934/dcds.2014.34.1061 [18] Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193 [19] Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99 [20] Junyoung Jang, Kihoon Jang, Hee-Dae Kwon, Jeehyun Lee. Feedback control of an HBV model based on ensemble kalman filter and differential evolution. Mathematical Biosciences & Engineering, 2018, 15 (3) : 667-691. doi: 10.3934/mbe.2018030

2020 Impact Factor: 0.935