Efficient Linear Multiparty PSI and Extensions to Circuit/Quorum PSI
Nishanth Chandran, Nishka Dasgupta, Divya Gupta, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar, Akash Shah
Abstract
Multiparty Private Set Intersection (mPSI), enables n parties, each holding private sets (each of size m) to securely compute the intersection of these private sets. While several protocols are known for this task, 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 O(nmtƛ), where t < n is the number of corrupt parties and ƛ is the security parameter. In this work, we make the following contributions:
Topics & Concepts
Intersection (aeronautics)Computer scienceProtocol (science)Task (project management)Set (abstract data type)Oblivious transferTheoretical computer scienceCryptographic protocolCommunication complexityWork (physics)Computer networkCryptographyComputer securityProgramming languageEngineeringMedicineAlternative medicineMechanical engineeringSystems engineeringPathologyAerospace engineeringCryptography and Data SecurityComplexity and Algorithms in Graphsgraph theory and CDMA systems