Secure and efficient multiparty private set intersection cardinality
Loading...
Authors
Debnath, Sumit Kumar
Stănică, Pantelimon
Kundu, Nibedita
Choudhury, Tanmay
Subjects
MPSI-CA
MPSI
semi-honest adversary
flexibility
Bloom filter
MPSI
semi-honest adversary
flexibility
Bloom filter
Advisors
Date of Issue
2021
Date
Publisher
American Institute of Mathematical Sciences
Language
Abstract
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(vmaxk) except that the complexity of the designated party is O(v1), where vmax is the maximum set size, v1 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(nvmaxk), 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.
Type
Article
Description
17 USC 105 interim-entered record; under review.
The article of record as published may be found at http://dx.doi.org/10.3934/amc.2020071
The article of record as published may be found at http://dx.doi.org/10.3934/amc.2020071
Series/Report No
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
22 p.
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.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.